Binary Search Trees Top Hash Tables Contents

Heaps

Synopsis

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. 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, greater than, or equal to its sibling.

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

Structure

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

Vocabulary

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.

Supports

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

Dependencies

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.

Operations

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.

heapify

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).

build-heap

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.

The build-heap operation takes 0 (n log n) time. Note that this is an upper bound, not a tight bound.

get-parent, get-left-child, get-right-child

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.

extract-min

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.

bubble-up

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.

insert

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).

peek

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

is-empty

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

Traversals

Heaps are generally not traversed.

Concept Inventory

Content to be added.

     
  1. This is a question.
    1. This is one possible answer
    2. This is another possible answer

lusth@cs.ua.edu


Binary Search Trees Top Hash Tables Contents