Return to search

Implementation of operations in double-ended heaps / Implementation of operations in double-ended heaps

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.

Identiferoai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:305073
Date January 2012
CreatorsBardiovský, Vojtech
ContributorsKoubek, Václav, Hubička, Jan
Source SetsCzech ETDs
LanguageEnglish
Detected LanguageEnglish
Typeinfo:eu-repo/semantics/masterThesis
Rightsinfo:eu-repo/semantics/restrictedAccess

Page generated in 0.0016 seconds