D-hip

Шаблон:Math-hip je struktura reda sa prioritetom, generalizacija Binarnog hipa u kojoj čvorovi imaju Шаблон:Math potomaka umesto 2. Dakle binarni hip je ustvari 2-hip. Prema Tarjan-u i Jensen-u, Шаблон:Math-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, Шаблон:Math-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 Шаблон:Math-hip radi u mestu tj. ne koristi nikakav dodatni prostor, pored potrebnog niza elemenata za hip.

Struktura d-hipa

Шаблон:Math-hip se sastoji od niza od Шаблон:Math elemenata, gde se svakom od elemenata dodeljuje i prioritet. Ti elementi mogu biti predstavljeni kao cvorovi u kompletnom Шаблон:Math-hip stablu, izlistani pomocu BFS-a : element niza na poziciji 0 predstavlja koren stabla, elemenati na poziciji 1-Шаблон:Math predstavljaju decu, sledecih Шаблон:Math su unuci, itd. Dakle, roditeljski cvor elementa na poziciji Шаблон:Math (za svako Шаблон:Math) je element na poziciji Шаблон:Math njegova deca su na pozicijama od Шаблон:Math do Шаблон:Math. 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 Шаблон:Math-hipu sa Шаблон:Math elemenata i smena niz stablo i smena uz stablo se mogu izvršiti najviše Шаблон:Math. 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 Шаблон:Math.U procesu smene niz stablo, svaka smena uključuje d poređenja i potrebno je Шаблон:Math vremena: Potrebno je Шаблон:Math 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 Шаблон:Math.

Prilokom kreiranja Шаблон:Math-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 Шаблон:Math elemenata nisu listovi, i mogu se procesom smene niz stablo smeniti samo jednom, i to za Шаблон:Math vremena koje je potrebno da se nađe dete koje bi se zamenilo sa tim čvorom. NajvišeШаблон:Math čvorova može biti smenjemo, procesom smene niz stablo, 2 puta, zauzimajući dodatnih Шаблон:Mathvremena 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}(\frac{n}{d^i}+1)O(d)=O(n).$

Tacna vrednost ove sume je ekvikalentana sledećem:

$\frac{d}{d-1}(n-s_d(n))-(d-1-(nmodd))(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 Шаблон:Math, 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 Шаблон:Math operacija brisanja minimuma i Шаблон:Math operacija za smanjenje prioriteta, gde je Шаблон:Math broj vrhova u grafu a m broj ivica. Korišćenjem Шаблон:Math-hipa sa Шаблон:Math, potrebno vreme za ova dva tipa operacija se može smanjiti do Шаблон:Math što je poboljšanje u odnosu na Шаблон:Math , š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 Шаблон:Math, ali u praksi Шаблон:Math-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 odШаблон:Math-hipa

Spoljašnje veze

• D-hip kod Шаблон:Wayback
• C++ implementacija d-hipa

Шаблон:Commonscat