Heaps

From

Revision as of 17:07, 9 April 2009

We have talked about a memory area called the heap. It is from this area that memory for dynamic allocation is taken. However, there is also a data structure called a heap. This data structure, while having the same name as the memory area, is different.

Heap Behavior

A heap is defined by two properties.

1. It must always be a complete binary tree.
   
2. It is partially ordered.
   

A complete binary tree means that all levels, with the possible exception of the lowest, are completely full. The lowest level is filled, in order from left to right. Because of this requirement, a heap is usually implemented as an array.

The second requirement—that of partial ordering—means that the value stored at every node is either less than or equal to the value stored in its children (this is called a min-heap) or the value stored in each node is greater than or equal to the value stored in its children (this is called a max-heap). As a result of this requirement, in a min-heap, the value stored in the root is always the smallest value in the heap, while the value stored in the root of a max-heap is always the largest value in the heap. For this reason, heaps are often used for the implementation of a priority queue.

Let us assume that we are going to build a min-heap. The process of building a heap is an operation sometimes called “heapify”. First, assume we have a complete binary tree of integers. Consider: 10 5 12 3 2 1 8 7 9 4.

Operation: bubble-down

To bubble-down a node, first compare the children of the node to find the smallest child (this is for a min-heap). If the node has no children, the operation ends. If the node has at least one child, the node is compared to the smallest child. If the parent node is smaller or equal to the child, the operation ends. If the parent is larger than the child, the parent and the child are swapped, and this operation is started again using the (former) parent node. Using this operation, a node will move down the tree, always swapping places with its smallest child, until it either becomes a leaf or it is smaller than its children.

Operation: heapify

This is the operation that creates a heap. We must start with a complete binary tree. Beginning with the level that is the parents of the leaves and starting with the rightmost node at this level, we perform the bubble-down operation on the rightmost node. When the bubble down operation has finished, we move to the second rightmost node at this level and perform the bubble down operation on that node. We continue in this manner, performing the bubble down operation on each node at this level moving from right to left. When all the nodes at this level have been bubbled-down, we move to the rightmost node of the next level above and repeat this procedure. We continue to bubble-down nodes at each level of the heap, moving from left to right and then moving up a level, until we have bubbled-down the root. At this point, we have a heap, and the heapify operation ends.

Operation: insert

To insert an element into a heap, place it at the next open leaf position and shift it upwards as far as it will go. This means to compare the node to its parent. If the node is smaller than its parent, the node changes places with the parent and we compare the node to its new parent. We continue this until the node is not smaller than its parent, and the operation ends.

Operation: delete

Elements are deleted from the heap only at the root. To delete the element, remove it from the root and replace it with the value stored in the right-most leaf. Then bubble-down this element to recreate the heap structure.

Common uses of a Heap

In addition to a priority queue, a heap is also used in a sorting algorithm called “heap sort”. In this algorithm, items to be sorted are stored in an array, which is then considered as a complete binary tree. The operation “heapify” is run on the array turning it into a max-heap or min-heap, and then the item at the root is repeatedly deleted and stored in the newly vacated array position. When all items have been deleted from the root, the array is sorted. While not the fastest sorting algorithm, heap-sort has the advantage of using little space. It only required space for the array plus one more slot.