Contents |

A heap is very much like a
binary search tree.
It is a
binary tree,
but the ordering of the values within
the tree differs.
While a
binary search tree
has the ordering: *left* `<`

*parent* `<`

*right*,
a heap has the ordering:
*parent* `<`

*left*,*right*
for a *min heap* and
*parent* `>`

*left*,*right*
for a *max heap*, all assuming no duplicates.
Note that, in a heap, the relationship between the values of
two siblings
is not specified. In practice,
a left child may be less than or greater than its
sibling, again assuming no duplicates.

When viewed as a tree, a heap is a complete binary tree.

class heap { var store; //store is usually an array //operations ... }

The terms used in describing a heap are:

- min heap
- With a min heap, the root is always the smallest element in the heap.
- min heap
- With a max heap, the root is always the largest element in the heap.

Heaps are used to partially sort elements. This property is exploited by the heapsort algorithm and by many graph search algorithms.

Heaps are usually based upon
arrays.
Academically speaking, they can be
based upon
binary trees
but this is rarely done since arrays work so well.
If a tree version of a heap is used,
an auxiliary data structure must be used
to ensure the desired time bound for the *extract-min*
operation.

The operation descriptions assume a min heap composed of unique values. For max heaps or for heaps with duplicate values, appropriate modifications to the descriptions should be made.

This operation begins by ensuring the value at the root of the heap is less than its children. If it is not, the root value is swapped with the minimum value, with respect to the children. The process continues by examining the child that received the root's value to ensure it is smaller than either of its children. If it is not, its value is swapped with the minimum value of its children and so on.

The heapify operation takes *Θ* (log *n*) time, since
the heap is a complete binary tree (and thus is balanced).

The build-heap operation turns an unordered complete
binary tree in the heap. It begins by running *heapify*
on each parent of the leaves. It continues by running
heapify on each grandparent of the leaves, and so on.
By working from the leaves upward to the root, the
smaller values are guaranteed to bubble upwards, with
the smallest value ending up at the root.

A naive analysis of the *build*-*heap* operation yields
an *0* (*n* log *n*) time bound.
Note that this bound is not tight.

For heaps based upon arrays, node values are stored in an array and the indices of that array are considered the node pointers. For example, the root node has index 0, the left child of the root has index 1, the right child of the root has index 2. In general, the index of the left child of any node is one more than twice the index of its parent and the index of the right child of any node is one more than the index of the left child.

To compute the parent index of a node *n*, simply subtract one
from *n*'s index and then divide the result
by two (integer division).

The *get-* operations can obviously be performed in constant time.

To extract the minimum value of a heap (which is found at the root, one first saves a pointer to the root value. Next, the rightmost leaf in the lowest layer is pruned from the heap and its value is used to replace the root's value. Finally, the heapify operation is performed on the root to ensure heap ordering is preserved.

This is why an array is so convenient for storing values in a heap.
The index of the rightmost leaf in the lowest layer is the last
index of the array. If there are *s* elements in the heap, the last
index is *s - 1*.

Pruning the rightmost leaf in the lowest layer devolves to reducing the perceived size of the array. Note that the array does not actually have to be reduced in size.

Since pruning takes constant time, the entire *extract-min* operation
takes *Θ* (log *n*) time since the operation is dominated
by *heapify*.

The *bubble*-*up*
operation, given an index, moves the value at that index
upwards towards the root, if needed. It swaps the value with the parent
if the value is less than the parent's, and then repeats the process
for the parent. The *bubble*-*up* operation is used if an insertion
operation is provided. Note that this operation ensures only
a single path in the heap adheres to heap ordering.

To insert a value into a heap of size *s*,
one bases
one places the new value into the heap at index *s*.
The size is then incremented to reflect the additional
element. The *bubble*-*up* operation is called on the new
value to ensure it rises to the proper level in the heap.

Insertion requires the heap be based upon a fillable array (for a bounded heap) or a dynamic array (for an unbounded heap).

The *peek* operation returns the value at the root of the heap.

This operation returns true if there are no elements in the heap and false otherwise.

Heaps are generally not traversed.

- This is a question.
- This is one possible answer
- This is another possible answer

Contents |