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

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

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

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

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

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

Структура[уреди | уреди извор]

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

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

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

Операције[уреди | уреди извор]

find-min(пронађи минимум)[уреди | уреди извор]

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

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

merge(спајање)[уреди | уреди извор]

Спајање са празним хипом враћа други хип, иначе враћа нови хип који као коренски елемент има минимум од два коренска елемента и само додаје хип са већим кореном у листу под-хипова.^[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(Уметање)[уреди | уреди извор]

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

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

Референце[уреди | уреди извор]

^ Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. стр. 231.
^ ^а ^б 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. стр. 63—77. ISBN 978-3-540-67690-4. arXiv:1110.4428 . doi:10.1007/3-540-44985-X_5. Архивирано из оригинала (PDF) 24. 12. 2012. г. Приступљено 28. 03. 2016.
^ ^а ^б 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, 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. Архивирано из оригинала (PDF) 21. 07. 2011. г. Приступљено 31. 05. 2015.
^ Pettie, Seth (2005), „Towards a final analysis of pairing heaps” (PDF), Proc. 46th Annual IEEE Symposium on Foundations of Computer Science, стр. 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, стр. 400—411, ISBN 978-3-540-54343-5, doi:10.1007/BFb0028279, CiteSeerX: 10.1.1.53.5960

Литература[уреди | уреди извор]

Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. стр. 231.

Спољашње везе[уреди | уреди извор]

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, Архивирано из оригинала (PDF) 18. 10. 2012. г., Приступљено 28. 05. 2015

[mehlhorn-1] Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox. Springer. стр. 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. стр. 63—77. ISBN 978-3-540-67690-4. arXiv:1110.4428 . doi:10.1007/3-540-44985-X_5. Архивирано из оригинала (PDF) 24. 12. 2012. г. Приступљено 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. Архивирано из оригинала (PDF) 21. 07. 2011. г. Приступљено 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, стр. 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, стр. 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]