Uparujući hip
Uparujući hip je tip strukture podataka sa relativno jednostavnom implementacijom kao i sa odličnim, optimizovanim performansama. Uparujući hipovi su višestruke strukture stabala, uređene hipovski i mogu se smatrati pojednostavljenim Fibonačijevim hipovima. Smatraju se "grubim izborom" za implementaciju algoritama poput Primovog MST algoritma i podržavaju sledeće operacije [1] :
- find-min(pronađi minimum) : vraća elemnet sa vrha hipa.
- merge(spajanje): upoređuje dva elementa u korenu, manji element ostaje koren rezultata, dok se veći element i njegovo podstablo dodaju kao potomak tog korena.
- insert(umetanje): kreiranje novog hipa od unetog elementa i vršenje merge operacije nad tim elementom sa postojećim, originalnim hipom.
- decrease-key(smanjenje ključa)(opciono): uklanja korensko podstablo čiji se ključ smanjuje, zamenjuje ključ sa manjim ključem a zatim se rezultat nakon spajanja vraća u hip.
- delete-min(brisanje minimuma): uklanja koren i spaja njegova podstabla. Koristi se više različitih strategija.
Analiza vremenske složenosti uparujućih hipova je inicijalno inspirisana "raširenim" stablima[2]. Složenost za delete-min iznosi . Operacije find-min, merge, i insert se izvršavaju u konstantnom vremenu, [3].
Ispostavilo se da je izračunavanje preciznog asimptotskog vremena izvršavanja uparujućih hipova kada je potrebna decrease-key operacija, komplikovano. Nagađa se da je vremenska složenost ove operacije [4], ali je Fredman dokazao da je vremenska složenost bar [5]. Peti je onda izveo gornju granicu koja je , optimizovano vreme za decrease-key iznosi [6].
Iako je ovo lošija složenost u poređenju sa drugim "priority queue" algoritmima kao što su Fibonačijevi hipovi, gde je složenost decrease-key , performansa u praksi je izvanredna. Stasko, Viter[4], Moret i Šapiro[7] su sproveli eksperiment nad uparujućim hipovima i drugim hip strukturama podataka. Došli su do zaključka da su uparujući hipovi bar podjednako brzi ali u većini slučajeva i brži u poređenju sa drugim efikasnim strukturama podataka kao što su binarni hipovi.
Struktura
Uparujući hipovi su ili prazni hipovi ili par koji se sastoji od korenskog elementa i verovatno praznom listom uparujućih hipova. Osobina uređenja hipa zahteva da svi korenski elementi pod-hipova u listi ne budu manji od korenskog elementa hipa. U opisu koji sledi pretpostavlja se da je reč o čisto funkcionalnom hipu koji ne podržava decrease-key operaciju.
type PairingHeap[Elem] = Empty | Heap(elem: Elem, subheaps: List[PairingHeap[Elem]])
Implementacija RAM mašina bazirana na pokazivačima koja podržava decrease-key može biti postignuta korišćenjem tri pokazivača po čvoru, predstavljajući potomka čvora kao jednostruko povezanu listu; pokazivač na prvi potomak čvora, jedan na njegovog bliskog/susednog rođaka (eng. sibling) i jedan na njegovog roditelja. Alternativa je da pokazivač na roditelja bude izostavljen, poslednji potomak će pokazivati na roditelja ako se doda zastavica koja će označavati kraj liste. Ovime se postiže kompaktnija struktura po cenu konstantnog faktora po operaciji[2].
Operacije
find-min(pronađi minimum)
funkcija find-min jednostavno vraža korenski element hipa.
function find-min(heap) if heap == Empty error else return heap.elem
merge(spajanje)
Spajanje sa praznim hipom vraća drugi hip, inače vraća novi hip koji kao korenski element ima minimum od dva korenska elementa i samo dodaje hip sa većim korenom u listu pod-hipova.[5]
function merge(heap1, heap2) if heap1 == Empty return heap2 elsif heap2 == Empty return heap1 elsif heap1.elem < heap2.elem return Heap(heap1.elem, heap2 :: heap1.subheaps) else return Heap(heap2.elem, heap1 :: heap2.subheaps)
insert(Umetanje)
Najjednostavniji način umetanja elementa u hip je spajanje hipa sa novim hipom koji sadrži samo željeni element i praznu listu pod-hipova.
function insert(elem, heap) return merge(Heap(elem, []), heap)
delete-min(brisanje minimuma)
Jedina netrivijalna fundamentalna operacija je brisanje minimalnog elemnta hipa. Standardna strategija je da se prvo spoje podhipovi u parove (po ovom koraku je struktura dobila ime uparujući hipovi) sa leva u desno a zatim spaja listu hipova sa desna u levo.
function delete-min(heap) if heap == Empty error else return merge-pairs(heap.subheaps)
Koristimo pomoćnu funkciju merge-pairs(spajanje parova):
function merge-pairs(l) if length(l) == 0 return Empty elsif length(l) == 1 return l[0] else return merge(merge(l[0], l[1]), merge-pairs(l[2.. ]))
Ispod je prikazano da je ovo zaista implementirano kao u opisu iznad, odnosno kao dva prolaza, sa leva u desno i sa desna u levo.
merge-pairs([H1, H2, H3, H4, H5, H6, H7]) => merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7])) # merge H1 and H2 to H12, then the rest of the list => merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7]))) # merge H3 and H4 to H34, then the rest of the list => merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7])))) # merge H5 and H6 to H56, then the rest of the list => merge(H12, merge(H34, merge(H56, H7))) # switch direction, merge the last two resulting heaps, giving H567 => merge(H12, merge(H34, H567)) # merge the last two resulting heaps, giving H34567 => merge(H12, H34567) # finally, merge the first merged pair with the result of merging the rest => H1234567
Reference
- ↑ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. str. 231.
- ↑ 2,0 2,1 Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). „The pairing heap: a new form of self-adjusting heap”. Algorithmica 1 (1): 111–129. DOI:10.1007/BF01840439.
- ↑ Iacono, John (2000). „Improved upper bounds for pairing heaps”. Lecture Notes in Computer Science. 1851. Proc. 7th Scandinavian Workshop on Algorithm Theory. Springer-Verlag. pp. 63–77. arXiv:1110.4428. DOI:10.1007/3-540-44985-X_5. ISBN 978-3-540-67690-4. Arhivirano iz originala na datum 24. 12. 2012. Pristupljeno 28. 03. 2016.
- ↑ 4,0 4,1 Stasko, John T.; Vitter, Jeffrey S. (1987), „Pairing heaps: experiments and analysis”, Communications of the ACM 30 (3): 234–249, DOI:10.1145/214748.214759, CiteSeerX: 10.1.1.106.2988
- ↑ 5,0 5,1 Fredman, Michael L. (1999). „On the efficiency of pairing heaps and related data structures”. Journal of the ACM 46 (4): 473–501. DOI:10.1145/320211.320214. Arhivirano iz originala na datum 21. 07. 2011. Pristupljeno 31. 05. 2015.
- ↑ Pettie, Seth (2005), „Towards a final analysis of pairing heaps”, Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 174–183, DOI:10.1109/SFCS.2005.75, ISBN 0-7695-2468-0
- ↑ Moret, Bernard M. E.; Shapiro, Henry D. (1991), „An empirical analysis of algorithms for constructing a minimum spanning tree”, Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 519, Springer-Verlag, pp. 400–411, DOI:10.1007/BFb0028279, ISBN 3-540-54343-0, CiteSeerX: 10.1.1.53.5960
Literatura
- Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. str. 231.
Spoljašnje veze
- Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (pp. 37–52).
- pairing heaps, Sartaj Sahni
- Elmasry, Amr (2009), „Pairing Heaps with O(log log n) decrease Cost”, Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms {SODA '09} (New York): 471–476, arhivirano iz originala na datum 18. 10. 2012, pristupljeno 28. 05. 2015