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 17 December 2004.
HTML page formatted Mon Sep 11 09:46:09 2006.

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. 17 December 2004. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/weakheap.html