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  :
* **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.
Složenost za delete-min iznosi  O(\log n)  . Operacije find-min, merge, i insert se izvršavaju u konstantnom vremenu,  O(1) .

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) , ali je Fredman dokazao da je vremenska složenost bar  \Omega(\log\log n). Peti je onda izveo gornju granicu koja je  O(2^{2\sqrt{\log\log n}}) , optimizovano vreme za decrease-key iznosi  O(\log n) .

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, Moret i Šapiro 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.

## 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.

 **function** merge(heap1, heap2)
   **if** heap1 == Empty
     **return** heap2
   **elsif** heap2 == Empty
     **return** heap1
   **elsif** heap1.elem  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

## Literatura
* 

## Vanjske veze
* Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (pp.&nbsp;37–52).
* pairing heaps, Sartaj Sahni
*