D-hip

D-hip je struktura reda sa prioritetom, generalizacija Binarnog hipa u kojoj čvorovi imaju d potomaka umesto 2. Dakle binarni hip je ustvari 2-hip. Prema Tarjan-u i Jensen-u, d-hip je izmišljen od strane Donald B. Johnson još 1975.

Ova struktura podataka omogućava da operacije smanjena prioriteta budu izvršavane brže nego u binarnom hipu, po cenu usporavanja operacije za brisanje minimuma. Ova izmena dovodi do bržeg izvršavanja algoritama kao sto su Dajkstra algoritam u kom su operacije smanjena prioriteta česće nego brisanja minimuma. Pored toga, d-hip ima i ponašanje pogodnije za keš memoriju nego binarni hip, što mu omogućava brže izvršavanje u praksi, bez obzira što teoriski ima širi najgori slučaj. Kao i binarni hip, tako i d-hip radi u mestu tj. ne koristi nikakav dodatni prostor, pored potrebnog niza elemenata za hip.

Struktura d-hipa

D-hip se sastoji od niza od n elemenata, gde se svakom od elemenata dodeljuje i prioritet. Ti elementi mogu biti predstavljeni kao cvorovi u kompletnom d-hip stablu, izlistani pomocu BFS-a : element niza na poziciji 0 predstavlja koren stabla, elemenati na poziciji 1-d predstavljaju decu, sledecih d² su unuci, itd. Dakle, roditeljski cvor elementa na poziciji i (za svako i > 0) je element na poziciji floor((i − 1)/d) njegova deca su na pozicijama od di + 1 do di + d. Prema obliku hipa: u min-hipu svaki element ima (vrednost) prioritet koja je veca ili jednaka od (vrednosti) prioriteta njegovih roditelja; u max-hipu svaki element ima prioritet veci nego njegovi roditelji.

Element minimalnog prioriteta u min-hipu (ili elemrnt maksimalnog prioriteta u max-hipu) uvek se nalazi na 0 poziciji u nizu. Da bi izbrisali ovaj element, poslednji element x u nizu se pomera na mesto 0-tog elementa, a duzina niza se smanjuje za jedan. Zatim se, sve dok ne ispuni uslove hipa, element x zamenjuje sa nekim njegovim potomkom (onim sa najmanjim prioritetom u min-hipu ili onim sa najvećim prioritetom u max-hipu), spuštajuci se niz stablo i pozicije u nizu. Ista ta smena niz stablo moze da se koristi i za uvećanje prioriteta elemenata u min-hipu ili za smanjenje prioriteta elemenata u max-hipu.

Da bi se dodao novi element u hip, on se ubacuje na kraj niza, a zatim se penje smenjujući se sa svojim roditeljima sve dok oblik hipa ne bude zadovoljen. Ova ista smena uz stablo može biti korisćena i za smanjenje prioriteta elemenata u min-hipu ili uvećanje prioriteta u max-hipu.

Da bi se kreirao novi hip od niza n elemenata, treba krenuti obrnutim redosldom, od elementa na n-1 poziciji pa sve do 0 elementa, primenjujući smenu niz stablo za svaki element.

Analiza

U d-hipu sa n elemenata i smena niz stablo i smena uz stablo se mogu izvršiti najviše log_d n = log n / log d. U procesu smene uz stablo svaka smena uključuje jedno poređenje elementa sa svojim roditeljem, i to se radi u konstantnom vremenu. Zbog toga, vreme potrebno: za dodavanje novog elementa u hip, da se smanji prioritet nekog elementa u min-hipu, ili da se poveca prioritet u max-hipu je O(log n / log d).U procesu smene niz stablo, svaka smena uključuje d poređenja i potrebno je O(d) vremena: Potrebno je d − 1 poređenje da se odredi minimum ili maximum dece nekog čvora, a zatim se taj čvor poredi sa roditeljem i utvrđuje se da li je potrebna smena ta dva čvora. Zbog toga, vreme potrebno da se izbriše koren, ili da se uvecea prioritet nekog elementa u min-hipu, ili da se smanji prioritet elementa u max-hipu je O(d log n / log d).

Prilokom kreiranja d-hipa od n elemenata , većina tih elemenata je na poziciji na kojoj će se vremenom naci listovi d-stabla, pa nije potrebno vršiti smenu niz stablo za te elemente. Najviše n/d + 1 elemenata nisu listovi, i mogu se procesom smene niz stablo smeniti samo jednom, i to za O(d) vremena koje je potrebno da se nađe dete koje bi se zamenilo sa tim čvorom. Najvišen/d² + 1 čvorova može biti smenjemo, procesom smene niz stablo, 2 puta, zauzimajući dodatnih O(d)vremena potrebnog da se izvrši još jedna smena, itd. Dakle, najaveće potrebno vreme da se hip kreira na ovaj načina je :

$\sum _{i=1}^{\log _{d}n}\left({\frac {n}{d^{i}}}+1\right)O(d)=O(n).$

Tacna vrednost ove sume je ekvikalentana sledećem:

${\frac {d}{d-1}}(n-s_{d}(n))-(d-1-(n\mod d))(e_{d}(\lfloor {\frac {n}{d}}\rfloor )+1)$,

s_d(n) je suma svih brojeva standardne osnove d reprezentacije n i e_d(n) exponent od d u faktoeizaciji od n.

Ovo se redukuje u:

$2n-2s_{2}(n)-e_{2}(n)$,

za d=2 i u

${\frac {3}{2}}(n-s_{3}(n))-2e_{3}(n)-e_{3}(n-1)$,

za d=3.

Prostor poterban za d-hip, sa insert i delete-min operacijama je lineran, pošto ne koristi nikakv dodatni prostor pored niza koji sadrži listu elemenata u hipu. Ako želimo da izmene prioriteta postojecih elemenata budu podržane, onda elementi moraju da sadrže i pokazivače na pozicije u hipu, koji takođe koriste linearan prostor.

Aplikacije

Dajkstra algoritam za nalaženje najkraćeg puta u grafu i Primov algoritam za minimalno razapinjuće stablo koriste min-hip u kom je n operacija brisanja minimuma i m operacija za smanjenje prioriteta, gde je n broj vrhova u grafu a m broj ivica. Korišćenjem d-hipa sa d = m/n, potrebno vreme za ova dva tipa operacija se može smanjiti do O(m log_m/n n) što je poboljšanje u odnosu na O(m log n) , što je vreme izvršavanja u binarnom hipu kada je broj ivica veći od broja vrhova. Alternativana struktura je Fibonači hip, koji teoriski daje još bolje vreme izvršavanja O(m + n log n), ali u praksi d-hip je najmanje isto toliko brz, a često i brži od Fibonači hipa za ove aplikacije.

4-hip može da pruži bolje performanse u praksi od binarnog hipa, čak i za operacije brisanja minimiuma. Dodatno, {{math|d}-hip se izvrsava mnogo brze nego Binarni hip za velicine hipa koja prekoracuju velicinu kes memorije:

Binatni hip zahteva više promašaj keša i vise pogrešnih strana virtualne memorije odd-hipa

Spoljašnje veze

• D-hip kod
• C++ implementacija d-hipa