A heap is a a type of tree. It is mostly useful as an implementation of a priority queue, and it is also the data structures used in heapsort.

A heap is a binary tree with the properties that it is perfectly balanced and that any node is larger than both its children (or smaller than both its children - you can choose which definition to use based on the problem at hand). The operations that can be performed on a heap are insertion of an item into the heap and removal of the root of the heap.

Although a heap is a tree, it is well suited to an array representation: The
root is element 1, and the children of node `i` are `2i` and
`2i+1`. For example:

- Add the new element to the next available slot / next array index.
- While the element is greater than its parent, swap it with the parent.

- Replace the root with the last element.
- While this element is smaller than either of its children, swap it with the larger child (if there are two children).

Last updated Sun Nov 28 22:04:38.0000000000 2004. Copyright Bruce Merry (bmerry '@' gmail dot. com).