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 $O(\log n)$ . Operacije find-min, merge, i insert se izvršavaju u konstantnom vremenu, $O(1)$ ^[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 $O(1)$ ^[4], ali je Fredman dokazao da je vremenska složenost bar $\Omega (\log \log n)$ ^[5]. Peti je onda izveo gornju granicu koja je $O(2^{2{\sqrt {\log \log n}}})$ , optimizovano vreme za decrease-key iznosi $O(\log n)$ ^[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 $O(1)$ , 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 udesno a zatim spaja listu hipova zdesna ulevo.

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, sleva udesno i zdesna ulevo.

   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.
^ ^a ^b Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). „The pairing heap: a new form of self-adjusting heap” (PDF). Algorithmica. 1 (1): 111—129. doi:10.1007/BF01840439.
^ Iacono, John (2000). Improved upper bounds for pairing heaps (PDF). Proc. 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science. 1851. Springer-Verlag. str. 63—77. ISBN 978-3-540-67690-4. arXiv:1110.4428  . doi:10.1007/3-540-44985-X_5. Arhivirano iz originala (PDF) 24. 12. 2012. g. Pristupljeno 28. 03. 2016.
^ ^a ^b 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
^ ^a ^b Fredman, Michael L. (1999). „On the efficiency of pairing heaps and related data structures” (PDF). Journal of the ACM. 46 (4): 473—501. doi:10.1145/320211.320214. Arhivirano iz originala (PDF) 21. 07. 2011. g. Pristupljeno 31. 05. 2015.
^ Pettie, Seth (2005), „Towards a final analysis of pairing heaps” (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, str. 174—183, ISBN 978-0-7695-2468-9, doi:10.1109/SFCS.2005.75
^ 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, str. 400—411, ISBN 978-3-540-54343-5, doi:10.1007/BFb0028279, 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” (PDF), Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms {SODA '09}, New York: 471—476, Arhivirano iz originala (PDF) 18. 10. 2012. g., Pristupljeno 28. 05. 2015

[mehlhorn-1] Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. str. 231.

[FSST-2] Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). „The pairing heap: a new form of self-adjusting heap” (PDF). Algorithmica. 1 (1): 111—129. doi:10.1007/BF01840439.

[Iacono2-3] Iacono, John (2000). Improved upper bounds for pairing heaps (PDF). Proc. 7th Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science. 1851. Springer-Verlag. str. 63—77. ISBN 978-3-540-67690-4. arXiv:1110.4428  . doi:10.1007/3-540-44985-X_5. Arhivirano iz originala (PDF) 24. 12. 2012. g. Pristupljeno 28. 03. 2016.

[StaskoVitter-4] 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

[Fredman-5] Fredman, Michael L. (1999). „On the efficiency of pairing heaps and related data structures” (PDF). Journal of the ACM. 46 (4): 473—501. doi:10.1145/320211.320214. Arhivirano iz originala (PDF) 21. 07. 2011. g. Pristupljeno 31. 05. 2015.

[Pettie-6] Pettie, Seth (2005), „Towards a final analysis of pairing heaps” (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, str. 174—183, ISBN 978-0-7695-2468-9, doi:10.1109/SFCS.2005.75

[MoretShapiro-7] 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, str. 400—411, ISBN 978-3-540-54343-5, doi:10.1007/BFb0028279, CiteSeerX: 10.1.1.53.5960

[1]

[2]

[3]

[4]

[5]

[6]

[7]