Упарујући хип

Упарујући хип је тип структуре података са релативно једноставном имплементацијом као и са одличним, оптимизованим перформансама. Упарујући хипови су вишеструке структуре стабала, уређене хиповски и могу се сматрати поједностављеним Фибоначијевим хиповима. Сматрају се "грубим избором" за имплементацију алгоритама попут Примовог МСТ алгоритма и подржавају следеће операције  :

• find-min(пронађи минимум) : враћа елемнет са врха хипа.
• merge(спајање): упоређује два елемента у корену, мањи елемент остаје корен резултата, док се већи елемент и његово подстабло додају као потомак тог корена.
• insert(уметање): креирање новог хипа од унетог елемента и вршење merge операције над тим елементом са постојећим, оригиналним хипом.
• decrease-key(смањење кључа)(опционо): уклања коренско подстабло чији се кључ смањује, замењује кључ са мањим кључем а затим се резултат након спајања враћа у хип.
• delete-min(брисање минимума): уклања корен и спаја његова подстабла. Користи се више различитих стратегија.

Анализа временске сложености упарујућих хипова је иницијално инспирисана "раширеним" стаблима. Сложеност за delete-min износи $O(\log n)$ . Операције find-min, merge, i insert се извршавају у константном времену, $O(1)$.

Испоставило се да је израчунавање прецизног асимптотског времена извршавања упарујућих хипова када је потребна decrease-key операција, компликовано. Нагађа се да је временска сложеност ове операције $O(1)$, али је Фредман доказао да је временска сложеност бар $\Omega (\log \log n)$. Пети је онда извео горњу границу која je $O(2^{2{\sqrt {\log \log n}}})$, оптимизовано време за decrease-key износи $O(\log n)$.

Иако је ово лошија сложеност у поређењу са другим "priority queue" алгоритмима као што су Фибоначијеви хипови, где је сложеност decrease-key $O(1)$ , перформанса у пракси је изванредна. Стаско, Витер, Морет и Шапиро су спровели експеримент над упарујућим хиповима и другим хип структурама података. Дошли су до закључка да су упарујући хипови бар подједнако брзи али у већини случајева и бржи у поређењу са другим ефикасним структурама података као што су бинарни хипови.

Структура

Упарујући хипови су или празни хипови или пар који се састоји од коренског елемента и вероватно празном листом упарујућих хипова. Особина уређења хипа захтева да сви коренски елементи под-хипова у листи не буду мањи од коренског елемента хипа. У опису који следи претпоставља се да је реч о чисто функционалном хипу који не подржава decrease-key операцију.

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

Имплементација РАМ машина базирана на показивачима која подржава decrease-key може бити постигнута коришћењем три показивача по чвору, представљајући потомка чвора као једноструко повезану листу; показивач на први потомак чвора, један на његовог блиског/суседног рођака (енг. sibling) и један на његовог родитеља. Алтернатива је да показивач на родитеља буде изостављен, последњи потомак ће показивати на родитеља ако се дода заставица која ће означавати крај листе. Овиме се постиже компактнија структура по цену константног фактора по операцији.

Операције

find-min(пронађи минимум)

функција find-min једноставно вража коренски елемент хипа.

function find-min(heap)
  if heap == Empty
    error
  else
    return heap.elem

merge(спајање)

Спајање са празним хипом враћа други хип, иначе враћа нови хип који као коренски елемент има минимум од два коренска елемента и само додаје хип са већим кореном у листу под-хипова.

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(Уметање)

Најједноставнији начин уметања елемента у хип је спајање хипа са новим хипом који садржи само жељени елемент и празну листу под-хипова.

function insert(elem, heap)
  return merge(Heap(elem, []), heap)

delete-min(брисање минимума)

Једина нетривијална фундаментална операција је брисање минималног елемнта хипа. Стандардна стратегија је да се прво споје подхипови у парове (по овом кораку је структура добила име упарујући хипови) са лева у десно а затим спаја листу хипова са десна у лево.

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

Користимо помоћну функцију merge-pairs(спајање парова):

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

Испод је приказано да је ово заиста имплементирано као у опису изнад, односно као два пролаза, са лева у десно и са десна у лево.

   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

Спољашње везе

• Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (pp. 37–52).
• pairing heaps, Sartaj Sahni
• Amr Elmasry (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