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.[1]
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).[1][2]
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.[1]
Varijante
[уреди | уреди извор]Slučajan promešan hip je najjednostavnija forma implementacije promešanog hipa. Takođe postoje i:
Reference
[уреди | уреди извор]- ^ а б в A. Gambin and A. Malinowski. 1998. Randomized Meldable Priority Queues. In Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics (SOFSEM '98), Branislav Rovan (Ed.). Springer-Verlag, London, UK, UK, 344-349.
- ^ P. Morin, [1] Open Data Structures, pp. 191-