1.6. Heaps

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:

A binary heap

Insertion

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

Deleting the root

  1. Replace the root with the last element.
  2. While this element is smaller than either of its children, swap it with the larger child (if there are two children).
[Prev] [Next] [Up]

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