Изворни код странице D-hip

{{DISPLAYTITLE:''D''-hip}}
'''{{math|''D''}}'''-hip je [[Структура података|struktura]] reda sa prioritetom, generalizacija [[Binarni hip|Binarnog hipa]] u kojoj čvorovi imaju {{math|''d''}} potomaka umesto 2.<ref name="j75"/><ref name="t83"/><ref name="w07"/> Dakle binarni hip je ustvari 2-hip. Prema Tarjan-u<ref name="t83"/> i Jensen-u,<ref>{{citation
| last1 = Jensen
| first1 = C.
| last2 = Katajainen
| first2 = J.
| last3 = Vitale
| first3 = F.
| title = An extended truth about heaps
| url = http://www.cphstl.dk/Report/In-place-multiway-heaps/experimental-study.pdf
| year = 2004
| accessdate = 17. 04. 2014
| archive-date = 09. 06. 2007
| archive-url = https://web.archive.org/web/20070609095910/http://www.cphstl.dk/Report/In-place-multiway-heaps/experimental-study.pdf
| url-status = dead
}}</ref> {{math|''d''}}-hip je izmišljen od strane [[Donald B. Johnson]] još 1975.<ref name="j75">{{citation
|last=Johnson| first = D. B. | authorlink = Donald B. Johnson
| doi = 10.1016/0020-0190(75)90001-0
| journal = Information Processing Letters|pages=53-57
| title = Priority queues with update and finding minimum spanning trees
| volume = 4
|year=1975
| issue = 3}}</ref>

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.<ref name="j75"/><ref name="t2"/> Pored toga, {{math|''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.<ref name="nmm91"/><ref name="k10"/> Kao i binarni hip, tako i {{math|''d''}}-hip radi u mestu tj. ne koristi nikakav dodatni prostor, pored potrebnog niza elemenata za hip.<ref name="t83"/><ref name="mp05">{{citation
|last1=Mortensen| first1 = C. W.
|last2=Pettie| first2 = S.
| contribution = The complexity of implicit and space efficient priority queues
| doi = 10.1007/11534273_6|pages=49-60
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = [[SWAT and WADS conferences|Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings]]
| volume = 3608
|year=2005|isbn=978-3-540-28101-6|pages=}}</ref>

== Struktura d-hipa ==
{{math|''D''}}-hip se sastoji od niza od {{math|''n''}} elemenata, gde se svakom od elemenata dodeljuje i prioritet. Ti elementi mogu biti predstavljeni kao cvorovi u kompletnom {{math|''d''}}-hip stablu, izlistani pomocu [[BFS]]-a : element niza na poziciji 0 predstavlja koren stabla, elemenati na poziciji 1-{{math|''d''}} predstavljaju decu, sledecih {{math|''d''<sup>2</sup>}} su unuci, itd. Dakle, roditeljski cvor elementa na poziciji {{math|''i''}} (za svako {{math|''i'' > 0}}) je element na poziciji {{math|floor((''i'' &minus; 1)/''d'')}} njegova deca su na pozicijama od {{math|''di'' + 1}} do {{math|''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.<ref name="t83">{{citation  
|last=Tarjan| first = R. E. | author-link = Robert Tarjan
| contribution = 3.2. ''d''-heaps|pages=34-38
| publisher = [[Society for Industrial and Applied Mathematics]]
| series = CBMS-NSF Regional Conference Series in Applied Mathematics
| title = Data Structures and Network Algorithms
| volume = 44
|year=1983}}</ref><ref name="w07"/>

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.<ref name="t83"/><ref name="w07"/>

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.<ref name="t83"/><ref name="w07"/>

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.<ref name="t83"/><ref name="w07"/>

== Analiza ==
U {{math|''d''}}-hipu sa {{math|''n''}} elemenata i smena niz stablo i smena uz stablo se mogu izvršiti najviše {{math|1=log<sub>''d''</sub> ''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 {{math|O(log ''n'' / log ''d'')}}.U procesu smene niz stablo, svaka smena uključuje ''d'' poređenja i potrebno je {{math|O(''d'')}} vremena: Potrebno je {{math|''d'' &minus; 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 {{math|O(''d'' log ''n'' / log ''d'')}}.<ref name="t83"/><ref name="w07"/>

Prilokom kreiranja {{math|''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 {{math|''n''/''d'' + 1}} elemenata nisu listovi, i mogu se procesom smene niz stablo smeniti samo jednom, i to za {{math|O(''d'')}} vremena koje je potrebno da se nađe dete koje bi se zamenilo sa tim čvorom. Najviše{{math|''n''/''d''<sup>2</sup> + 1}} čvorova može biti smenjemo, procesom smene niz stablo, 2 puta, zauzimajući dodatnih {{math|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 :
:<math>\sum_{i=1}^{\log_d n} \left(\frac{n}{d^i}+1\right) O(d) = O(n).</math><ref name="t83"/><ref name="w07"/>

Tacna vrednost ove sume je ekvikalentana sledećem:

:<math> \frac{d}{d-1} (n - s_d (n)) - (d-1 - (n  \mod  d)) ( e_d ( \lfloor \frac{n}{d} \rfloor) + 1) </math>,<ref name="Suchenek">{{citation
|last1=Suchenek| first1 = Marek A.
| title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
| doi = 10.3233/FI-2012-751|pages=75-92
| publisher = IOS Press
| journal = Fundamenta Informaticae
| volume = 120
| issue = 1
|year=2012
| url = http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU}}</ref>
s<sub>d</sub>(n) je suma svih brojeva standardne osnove ''d'' reprezentacije ''n'' i e<sub>d</sub>(n) exponent od ''d'' u faktoeizaciji od ''n''.

Ovo se redukuje u:
:<math> 2 n - 2 s_2 (n) - e_2 (n) </math>,<ref name="Suchenek" />
za d=2 i u

:<math> \frac{3}{2} (n - s_3 (n)) - 2 e_3 (n) - e_3 (n-1) </math>,<ref name="Suchenek" />

za d=3.


Prostor poterban za {{math|''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.<ref name="t83"/><ref name="mp05"/> 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.
<ref name="t83"/>

== 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|''n''}} operacija brisanja minimuma i {{math|''m''}} operacija za smanjenje prioriteta, gde je {{math|''n''}} broj vrhova u grafu a ''m'' broj ivica. Korišćenjem {{math|''d''}}-hipa sa {{math|1=''d'' = ''m''/''n''}}, potrebno vreme za ova dva tipa operacija se može smanjiti do {{math|O(''m'' log<sub>''m''/''n''</sub> ''n'')}} što je poboljšanje u odnosu na {{math|O(''m'' log ''n'')}} , što je vreme izvršavanja u binarnom hipu kada je broj ivica veći od broja vrhova.<ref name="j75"/><ref name="t2">{{harvnb|Tarjan|1983}}. стр. 77 and 91.</ref> Alternativana struktura je [[Fibonači hip]], koji teoriski daje još bolje vreme izvršavanja {{math|O(''m'' + ''n'' log ''n'')}}, ali u praksi {{math|''d''}}-hip je najmanje isto toliko brz, a često i brži od Fibonači hipa za ove aplikacije.<ref>{{citation
|last1=Cherkassky| first1 = B. V.
|last2=Goldberg| first2 = A. V. | author2-link = Andrew V. Goldberg
|last3=Radzik| first3 = T.
| doi = 10.1007/BF02592101
| issue = 2
| journal = Mathematical Programming|pages=129-174
| title = Shortest paths algorithms: Theory and experimental evaluation
| volume = 73
|year=1996}}</ref>

4-hip može da pruži bolje performanse u praksi od binarnog hipa, čak i za operacije brisanja minimiuma.<ref name="t83"/><ref name="w07">{{citation
|last=Weiss| first = M. A.
| contribution = ''d''-heaps
| edition = 2nd|isbn=978-0-321-37013-6
|pages=216
| publisher = Addison-Wesley
| title = Data Structures and Algorithm Analysis
|year=2007}}</ref> 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|''d''}}-hipa<ref name="nmm91">{{citation
|last1=Naor| first1 = D.
|last2=Martel| first2 = C. U.
|last3=Matloff| first3 = N. S.
|year=1991
| doi = 10.1093/comjnl/34.5.428
| issue = 5
| journal = Computer Journal|pages=428-437
| title = Performance of priority queue structures in a virtual memory environment
| volume = 34}}</ref><ref name="k10">{{citation
|last=Kamp| first = Poul-Henning
| journal = ACM Queue
| title = You're doing it wrong
| url = http://queue.acm.org/detail.cfm?id=1814327
| volume = 8
| issue = 6
|year=2010}}</ref>

== Reference ==
{{reflist}}

== Spoljašnje veze ==
* [http://en.algoritmy.net/article/41909/D-ary-heap D-hip kod] {{Wayback|url=http://en.algoritmy.net/article/41909/D-ary-heap |date=20140419025132 }}
* [https://github.com/valyala/gheap C++ implementacija d-hipa]

{{normativna kontrola}}

{{СОРТИРАЊЕ:Д-хип}}
{{Commonscat|Algorithms}}

[[Категорија:Strukture podataka]]