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.

A weak min-heap is similar, but reverses the required order relationship between the value at each node and in its right subtree.

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]

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 log₂n + O(n) comparisons.^[3][4] They were later investigated as a more generally applicable priority queue data structure.^[5][6]

References

1. Edelkamp, Stefan (26 May 2011), Pieterse, Vreda; Black, Paul E., eds., "weak-heap", Dictionary of Algorithms and Data Structures, retrieved 2015-12-01
2. Edelkamp, Stefan; Elmasry, Amr; Katajainen, Jyrki (2012), "The weak-heap data structure: variants and applications", Journal of Discrete Algorithms, 16: 187–205, doi:10.1016/j.jda.2012.04.010, MR 2960353.
3. Dutton, Ronald D. (1993), "Weak-heap sort", BIT, 33 (3): 372–381, doi:10.1007/bf01990520.
4. Edelkamp, Stefan; Wegener, Ingo (2000), "On the Performance of WEAK-HEAPSORT", Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS 2000), Lecture Notes in Computer Science, 1770, Springer-Verlag, pp. 254–266, doi:10.1007/3-540-46541-3_21.
5. 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, 6049, Springer-Verlag, pp. 424–435, doi:10.1007/978-3-642-13193-6_36.
6. 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.