Weak heap
A weak heap is a variation of the a binary heap data structure.
Description
A weak max-heap on a set of n values is defined to be a binary tree with n nodes, one for each value, satisfying the following constraints:[1]
- The root node has no left child
- For every node, the value associated with that node is greater or equal to than the values associated with all nodes in its right subtree.
- The leaves of the tree have heights that are all within one of each other.
These invariants are similar to a standard binary heap, but weaker because a node is not kept sorted with respect to its left subtree.
(A weak min-heap reverses the conditions in the obvious way.)
Priority queue operations
In a weak max-heap, the maximum value can be found (in constant time) as the value associated with the root node; similarly, in a weak min-heap, the minimum value can be found at the root.
As with binary heaps, weak heaps can support the typical operations of a priority queue data structure: insert, delete-min, delete, or decrease-key, in logarithmic time per operation. Variants of the weak heap structure allow constant amortized time insertions and decrease-keys, matching the time for Fibonacci heaps.[2]
Weak heaps may be used as an implicit data structure, but require the ability to exchange a node's children. This may be done with one bit per internal node of auxiliary storage to indicate the position of the children.
History and applications
Weak heaps were introduced by Dutton (1993), as part of a variant heap sort algorithm that (unlike the standard heap sort using binary heaps) could be used to sort n items using only n log2n + O(n) comparisons.[3][4] They were later investigated as a more generally applicable priority queue data structure.[5][6]
References
- ^ Edelkamp, Stefan (26 May 2011), Pieterse, Vreda; Black, Paul E. (eds.), "weak-heap", Dictionary of Algorithms and Data Structures, retrieved 2015-12-01
- ^ Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (October 2012), "The weak-heap data structure: variants and applications" (PDF), Journal of Discrete Algorithms, 16: 187–205, doi:10.1016/j.jda.2012.04.010, MR 2960353.
- ^ Dutton, Ronald D. (1993), "Weak-heap sort", BIT, 33 (3): 372–381, doi:10.1007/bf01990520.
- ^ Edelkamp, Stefan; Wegener, Ingo (2000), "On the Performance of WEAK-HEAPSORT", Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2000) (PDF), Lecture Notes in Computer Science, vol. 1770, Springer-Verlag, pp. 254–266, CiteSeerX 10.1.1.21.1863, doi:10.1007/3-540-46541-3_21.
- ^ Bruun, Asger; Edelkamp, Stefan; Katajainen, Jyrki; Rasmussen, Jens (2010), "Policy-Based Benchmarking of Weak Heaps and Their Relatives", Proceedings of the 9th International Symposium on Experimental Algorithms (SEA 2010), Lecture Notes in Computer Science, vol. 6049, Springer-Verlag, pp. 424–435, doi:10.1007/978-3-642-13193-6_36
{{citation}}: External link in|lay-url=|lay-url=ignored (help). - ^ Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2012), "The Weak-heap Family of Priority Queues in Theory and Praxis", Proceedings of the Eighteenth Computing: The Australasian Theory Symposium (CATS 2012), Volume 128, Darlinghurst, Australia, Australia: Australian Computer Society, Inc., pp. 103–112, ISBN 978-1-921770-09-8.