Original title:
Implementation of operations in double-ended heaps
Translated title:
Implementation of operations in double-ended heaps
Authors:
Bardiovský, Vojtech ; Koubek, Václav (advisor) ; Hubička, Jan (referee) Document type: Master’s theses
Year:
2012
Language:
eng Abstract:
[eng][cze] There are several approaches for creating double-ended heaps from the single-ended heaps. We build on one of them, the leaf correspondence heap, to create a generic double ended heap scheme called L-correspondence heap. This will broaden the class of eligible base single-ended heaps (e.g. by Fibonacci heap, Rank-pairing heap) and make the operations Decrease and Increase possible. We show this approach on specific examples for three different single-ended base heaps and give time complexity bounds for all operations. Another result is that for these three examples, the expected amortized time for Decrease and Increase operations in the L-correspondence heap is bounded by a constant.Existuje viacero spôsobov ako vytvoriť dvojkoncovú haldu z dvoch klasických háld. V tejto práci rozšírime dvojkoncovú haldu založenú na prepojení listov a vytvoríme novú schému nazvanú L-korešpondencia. Táto schéma rozšíri triedu možných klasických háld použiteľných pre vytvorenie dvojkoncovej haldy (napr. Fibonacci halda, Rank-pairing halda). Ďalej umožní operácie ``Zníž prioritu'' a ``Zvýš prioritu''. Tento prístup ukážeme na troch konkrétnych haldách a odhadneme časovú zložitosť pre všetky operácie. Ďalším výsledkom je, že pre tieto tri konkrétne haldy, očakávaný čas operácií ``Zníž prioritu'' a ``Zvýš prioritu'' je obmedzený konštantou.
Keywords:
complexity; decrease; double-ended priority queue; leaf correspondence; rank- paring heap; decrease; dvojkoncová halda; zložitosť
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/40770