D-hip — разлика између измена

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 17. април 2014. у 04:35

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

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.^[1]^[5] Pored toga, $d$ -hip ima i ponašanje pogodnije za keš memoriju nego binarni hip, što mu omogućava brže izvrašvanje u praksi, bez obzira što teoriski ima širi najgori slučaj.^[6]^[7] Kao i binarni hip, tako i $d$ -hip radi u mestu tj. ne koristi nikakav dodatni prostor, pored potrebnog niza elemenata za hip.^[2]^[8]

Struktura d-hipa

$D$ -hip se sastoji od niza od $n$ items, 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 2$ 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.^[2]^[3]

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.^[2]^[3]

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..^[2]^[3]

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.^[2]^[3]

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)$ .^[2]^[3]

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še $n / d 2 + 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).

^[2]^[3]

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)

,^[9]

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)

, ^[9]

za d=2 i u

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

,^[9]

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.^[2]^[8] 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. ^[2]

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.^[1]^[5] 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.^[10]

4-hip može da pruži bolje performanse u praksi od binarnog hipa, čak i za operacije brisanja minimiuma.^[2]^[3] Additionally, a {{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 $d$ -hipa^[6]^[7]

Reference

^ ^а ^б ^в ^г Johnson, D. B. (1975), „Priority queues with update and finding minimum spanning trees”, Information Processing Letters, 4 (3): 53—57, doi:10.1016/0020-0190(75)90001-0 .
^ ^а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и ^ј ^к Tarjan, R. E. (1983), „3.2. d-heaps”, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, 44, Society for Industrial and Applied Mathematics, стр. 34—38 .
^ ^а ^б ^в ^г ^д ^ђ ^е ^ж Weiss, M. A. (2007), „d-heaps”, Data Structures and Algorithm Analysis (2nd изд.), Addison-Wesley, стр. 216, ISBN 0-321-37013-9 .
^ Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF) .
^ ^а ^б Tarjan (1983), pp. 77 and 91.
^ ^а ^б Naor, D.; Martel, C. U.; Matloff, N. S. (1991), „Performance of priority queue structures in a virtual memory environment”, Computer Journal, 34 (5): 428—437, doi:10.1093/comjnl/34.5.428 .
^ ^а ^б Kamp, Poul-Henning (2010), „You're doing it wrong”, ACM Queue, 8 (6) .
^ ^а ^б Mortensen, C. W.; Pettie, S. (2005), „The complexity of implicit and space efficient priority queues”, Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, Lecture Notes in Computer Science, 3608, Springer-Verlag, стр. 49—60, ISBN 978-3-540-28101-6, doi:10.1007/11534273_6 .
^ ^а ^б ^в Suchenek, Marek A. (2012), „Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program”, Fundamenta Informaticae, IOS Press, 120 (1): 75—92, doi:10.3233/FI-2012-751 .
^ Cherkassky, B. V.; Goldberg, A. V.; Radzik, T. (1996), „Shortest paths algorithms: Theory and experimental evaluation”, Mathematical Programming, 73 (2): 129—174, doi:10.1007/BF02592101 .

Externi linkovi

[j75-1] а ^б ^в ^г Johnson, D. B. (1975), „Priority queues with update and finding minimum spanning trees”, Information Processing Letters, 4 (3): 53—57, doi:10.1016/0020-0190(75)90001-0 .

[t83-2] а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и ^ј ^к Tarjan, R. E. (1983), „3.2. d-heaps”, Data Structures and Network Algorithms, CBMS-NSF Regional Conference Series in Applied Mathematics, 44, Society for Industrial and Applied Mathematics, стр. 34—38 .

[w07-3] а ^б ^в ^г ^д ^ђ ^е ^ж Weiss, M. A. (2007), „d-heaps”, Data Structures and Algorithm Analysis (2nd изд.), Addison-Wesley, стр. 216, ISBN 0-321-37013-9 .

[4] Jensen, C.; Katajainen, J.; Vitale, F. (2004), An extended truth about heaps (PDF) .

[t2-5] а ^б Tarjan (1983), pp. 77 and 91.

[nmm91-6] а ^б Naor, D.; Martel, C. U.; Matloff, N. S. (1991), „Performance of priority queue structures in a virtual memory environment”, Computer Journal, 34 (5): 428—437, doi:10.1093/comjnl/34.5.428 .

[k10-7] а ^б Kamp, Poul-Henning (2010), „You're doing it wrong”, ACM Queue, 8 (6) .

[mp05-8] а ^б Mortensen, C. W.; Pettie, S. (2005), „The complexity of implicit and space efficient priority queues”, Algorithms and Data Structures: 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, Lecture Notes in Computer Science, 3608, Springer-Verlag, стр. 49—60, ISBN 978-3-540-28101-6, doi:10.1007/11534273_6 .

[Suchenek-9] а ^б ^в Suchenek, Marek A. (2012), „Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program”, Fundamenta Informaticae, IOS Press, 120 (1): 75—92, doi:10.3233/FI-2012-751 .

[10] Cherkassky, B. V.; Goldberg, A. V.; Radzik, T. (1996), „Shortest paths algorithms: Theory and experimental evaluation”, Mathematical Programming, 73 (2): 129—174, doi:10.1007/BF02592101 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Ред 1: / Ред 1: @@
 {{МАТФ032014}}
-{{DISPLAYTITLE:''d''-ary heap}}
+{{DISPLAYTITLE:''d''-hip}}
+'''{{math|''D''}}'''-hip je [[Структура података|struktura]] reda sa prioritetom, generalizacija [[Binarni hip|Binarnog hipa]] u kojoj čvorovi imaju {{math|''d''}} potpmaka 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}}.
+</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 izvrašvanje 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}}.</ref>
+==Struktura d-hipa==
+{{math|''D''}}-hip se sastoji od niza od {{math|''n''}} items, 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">{{harvtxt|Tarjan|1983}}, pp. 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>
+-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 = 0-321-37013-9
+ | page = 216
+ | publisher = Addison-Wesley
+ | title = Data Structures and Algorithm Analysis
+ | year = 2007}}.</ref> Additionally,
+a {{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}}
+==Externi linkovi==
+*[http://en.algoritmy.net/article/41909/D-ary-heap D-hip kod]
+*[https://github.com/valyala/gheap C++ implementacija d-hipa]
 [[Категорија:Strukture podataka]]