Uparujući hip
<s>Uparujući hip je tip strukture podataka sa relativno jednostavnom implementacijom kao i sa odličnim, optimizovanim performansama.</s><s>Uparujući hipovi su višestruke strukture stabala, uređene hipovski i mogu se smatrati pojednostavljenim Fibonačijevim hipovima.</s><s>Smatraju se "grubim izborom" za implementaciju algoritama poput Primovog MST algoritma i podržavaju sledeće operacije  :
 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.</s><s>Koristi se više različitih strategija.</s>

<s>Analiza vremenske složenosti uparujućih hipova je inicijalno inspirisana "raširenim" stablima.</s><s>Složenost za delete-min iznosi  .</s><s>Operacije find-min, merge, i insert se izvršavaju u konstantnom vremenu, .</s>

<s>Ispostavilo se da je izračunavanje preciznog asimptotskog vremena izvršavanja uparujućih hipova kada je potrebna decrease-key operacija, komplikovano.</s><s>Nagađa se da je vremenska složenost ove operacije , ali je Fredman dokazao da je vremenska složenost bar .</s><s>Peti je onda izveo gornju granicu koja je , optimizovano vreme za decrease-key iznosi .</s>

<s>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.</s><s>Stasko, Viter, Moret i Šapiro su sproveli eksperiment nad uparujućim hipovima i drugim hip strukturama podataka.</s><s>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.</s>

<s>Struktura</s>

<s>Uparujući hipovi su ili prazni hipovi ili par koji se sastoji od korenskog elementa i verovatno praznom listom uparujućih hipova.</s><s>Osobina uređenja hipa zahteva da svi korenski elementi pod-hipova u listi ne budu manji od korenskog elementa hipa.</s><s>U opisu koji sledi pretpostavlja se da je reč o čisto funkcionalnom hipu koji ne podržava decrease-key operaciju.</s>

<s>type PairingHeap[Elem] = Empty | Heap(elem: Elem, subheaps: List[PairingHeap[Elem]])</s>

<s>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.</s><s>Alternativa je da pokazivač na roditelja bude izostavljen, poslednji potomak će pokazivati na roditelja ako se doda zastavica koja će označavati kraj liste.</s><s>Ovime se postiže kompaktnija struktura po cenu konstantnog faktora po operaciji.</s>

<s>Operacije</s>

<s>find-min(pronađi minimum)</s>

<s>funkcija find-min jednostavno vraža korenski element hipa.</s>

<s>function find-min(heap)
   if heap == Empty
     error
   else
     return heap.elem</s>

<s>merge(spajanje)</s>

<s>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.</s>

<s>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)</s>

<s>insert(Umetanje)</s>

<s>Najjednostavniji način umetanja elementa u hip je spajanje hipa sa novim hipom koji sadrži samo željeni element i praznu listu pod-hipova.</s>

<s>function insert(elem, heap)
   return merge(Heap(elem, []), heap)</s>

<s>delete-min(brisanje minimuma)</s>

<s>Jedina netrivijalna fundamentalna operacija je brisanje minimalnog elemnta hipa.</s><s>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.</s>

<s>function delete-min(heap)
   if heap == Empty
     error
   else
     return merge-pairs(heap.subheaps)</s>

<s>Koristimo pomoćnu funkciju merge-pairs(spajanje parova):</s>

<s>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.. ]))</s>

<s>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.</s>

<s>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</s>

<s>Reference</s>

<s>Literatura</s>

<s>Spoljašnje veze 
 Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (pp.</s><s>37–52).
 pairing heaps, Sartaj Sahni</s>

<s>Strukture podataka</s>

