weak-heap

(data structure)

Definition: A relaxed heap satisfying the following three conditions: (1) every key in the right subtree of a node is greater than the key stored in the node itself, (2) the root has no left child, and (3) leaves are only found on the last two levels of the tree.

See also weak-heap sort.

Note: A weak-heap may be efficiently implemented with an array a of items and an array r of reverse bits. The left child of an index i is at index 2i+1-r_i, and the right child is at index 2i+r_i.

This is a minimum weak-heap. A maximum weak-heap has subtree keys that are less than the node's key.

Author: SE

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 26 May 2011.
HTML page formatted Mon Feb 2 13:10:40 2015.

Cite this as:
Stefan Edelkamp, "weak-heap", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 26 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/weakheap.html