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

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

Entry modified 26 May 2011.
HTML page formatted Thu May 26 15:59:49 2011.

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