Slučajan promešan hip

U informatici, slučajni promešani hip (takođe i promešani hip i slučajan promešan prioritetni red) je prioritetni red. Slučajni promešani hip je bazična struktura podataka u kojoj je osnovna struktura takođe hip-red binarno stablo. Kako god, nema ograničenja u obliku osnovnog binarnog stabla. Ovaj pristup ima brojna poboljšanja u odnosu na slične strukture podataka. Ova struktura nudi sjajna pojednostavljenja: sve operacije slučajnog promešanog hipa su lake za implementaciju i konstantni faktori u njenoj implementaciju su mali,takođe nema potrebe za čuvanjem uslova balansa.

Operacije

Slučajan promešan hip podržava izvestan broj zajedničkih operacija. To su umetanje,brisanje,operacija pretrage,pronalazak minimuma. Operacije umetanja i brisanja su implementirane u terminima dodatnih specifičnih operacija za promešan hip , Promešaj(Q1,Q2).

Mešanje

Osnovni cilj mešanja(takođe poznatog kao spajanje)je da uzmemo dva hipa(uzimajući od svakog hipa koren),Q1 i Q2 ,i spojiti ih,vraćajući sam hip čvor kao rezultat. Dobra odlika operacije mešanja je ta da može biti definisana rekurzivno. Ako su oba hipa prazna(pokazivač nil), tada metod jednostavno vraća koren nepraznog hipa. Ako oba (i Q1 i Q2) nisu nil ,proveriti da li je Q1>Q2. Ako jeste ,onda ih zamenimo. Zbog toga je sigurno da je Q1<Q2 i taj koren spojenog hipa će sadržati Q1. Onda rekurzivno spajamo Q2 sa Q1.Levo ili sa Q1.Desno.

function Promešati(Čvor Q1, Čvor Q2)
 if Q1 je nil => return Q2
 if Q2 je nil => return Q1
 if Q1 > Q2 => zameni Q1 and Q2
 if bacanje_novčića je 0 => Q1.levo = Promešati(Q1.levo, Q2)
 else Q1.desno = Promešati(Q1.desno, Q2)
 return Q1

Umetanje

Kada je operacija mešanja završena,umetanje u promešan hip je jednostavno. Prvo,novi čvor,u,je kreiran i sadrži vrednost x. Ovaj novi čvor je jednostavno promešan sa korenim čvorom hipa.

function Umetanje(x)
 Čvor u = new Čvor
 u.x = x
 koren = Promešati(u, koren)
 r.roditelj = nil
 povećaj broj čvorova

Brisanje

Slično kao i kod operacije umetanja.Brisanje() koristi operaciju mešanja da eliminiše koren iz hipa.Ovo se završava mešanjem dva deteta korenog čvora,i čvor koji se vraća je novi koren.

function Brisanje()
 koren = Promešati(koren.levo, koren.desno)
 if koren nije nil => koren.roditelj = nil
 smanji broj čvorova

Nalaženje minimuma

Verovatno najlakša operacija za slučajan promešan hip. NadjiMin() jednostavno vraća element koji je smešten u korenom čvoru hipa.

Dodatne operacije

Neke dodatne operacije mogu biti implementirane za promešan hip, a da imaju složenost O(logn) u najgorem slučaju. Te operacije su:

• Brisanje(u) - Briše sve čvorove u i njihove ključeve iz hipa.
• Apsorbovanje(Q) - dodaje sve elemente hipa Q u ovaj hip,takodje prazni Q u procesu
• SmanjenjeKljuča(u,y) - Smanjuje ključ u čvoru sa u na y (preuslov y<=u.x)

Analiza efikasnosti

Kako su sve nekonstantne vremenske operacije definisane u terminima operacije mešanja, efikasnost ovih operacija može biti odredjena kroz analizu kompleksnosti mešanja dva slučajna hipa. Od rezultata ove analize se očekuje da vreme operacije bilo kog promešanog prioritetnog reda na slučajnom hipu sa n čvorova bude O(log n).

Operacije	Vremenska efikasnost najgoreg slučaja
Promešati(Q1, Q2)	O(logn)
Umetanje(x)	O(logn)
Brisanje()	O(logn)
NadjiMin()	O(logn)
Brisanje(x)	O(logn)
Apsorbovanje(Q)	O(logn)

Istorija

Promešan hip je prvi put predložen 1998. od strane Gambina i Malinkoskog.

Varijante

Slučajan promešan hip je najjednostavnija forma implementacije promešanog hipa. Takođe postoje i:

• Binomni hip
• Fibonači hip