Heaps

From

Current revision as of 02:05, 16 May 2012

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.

Recall that in a binary tree each node can have a left child node and/or a right child node. A leaf is a node with no children.

An almost complete binary tree is a binary tree in which the following 3 conditions hold: all the leaves are at the bottom level or the bottom 2 levels, all the leaves are in the leftmost possible positions, and (except possibly for the bottom level) all levels are completely filled with nodes.

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.

Definition: A minimal heap (descending heap) is an almost complete binary tree in which the value at each parent node is less than or equal to the values in its child nodes.

Obviously, the minimum value is in the root node. Note, too, that any path from a leaf to the root passes through the data in descending order.

Here is an example of a minimal heap:

                  C

               /     \

             H         K

           /   \     /

          L     I   M

Representing Heaps

The typical storage method for a heap, or any almost complete binary tree, works as follows. Begin by numbering the nodes level by level from the top down, left to right. For example, consider the following heap. The numbering has been added below the nodes.

                  C
                  0
               /     \

             H         K
             1         2
           /   \     /

          L     I   M
          3     4   5

Then store the data in an array as shown below:

The advantage of this method over using the usual pointers and nodes is that there is no wasting of space due to storing two pointer fields in each node. Instead, starting with the current index, CI, one calculates the index to use as follows (div is whole number division):

Parent(CI) = (CI - 1) div 2
RightChild(CI) = 2 * (CI + 1)
LeftChild(CI) = 2 * CI + 1

For example, if we start at node H (with index 1), the right child is at index 2 * (1 + 1) = 4, that is, node I.

Heap Operations

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.

As an example, consider adding "E" to the heap shown below. This is done by temporarily placing the new item "E" at the end of the heap (array) and then calling a BubbleUp routine to make any needed adjustments on the path from this leaf to the root. For example, let's insert E into the following heap:

                  C

               /     \

             H         K

           /   \     /

          L     I   M

First, temporarily place E in the next available position:

                  C

               /     \

             H         K

           /   \     /   \

          L     I   M     E

Of course, the new tree might not be a heap. The BubbleUp routine now checks the parent, K, and sees that things would be out of order as they are. So K is moved down to where E was. Then the parent above that, C, is checked. It is in order relative to the target item E, so the C is not moved down. The hole left behind is filled with E, then, as this is the correct position for it.

                  C

               /     \

             H         E

           /   \     /   \

          L     I   M     K

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.

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.

We always remove the item from the root. That way we always get the smallest item from on Min-Heap, or the largest item from a Max-Heap . The problem is then how to adjust the binary tree so that we again have a heap (with one less item).

The algorithm works like this: First, remove the root item and replace it temporarily with the item in the last position. Call this replacement the target. A BubbleDown routine is then used to check the path from the root to a leaf for the correct position for this target. The path is chosen by always selecting the smaller child at each node. For example, let's remove the C from this heap:

                  C

               /     \

             D         E

           /   \     /   \

          H     I   M     K

        /

       L

First we remove the C and replace it with the last item (the target), L:

                  L

               /     \

             D         E

           /   \     /   \

          H     I   M     K

The smaller child of L is D. Since D is out of order compared to the target L, we move D up. The smaller child under where D had been is H. When H is compared to L we see that the H too needs to be moved up. Since we are now at a leaf, this empty leaf is where the target L is put.

                  D

               /     \

             H         E

           /   \     /   \

          L     I   M     K

Operation: heapify

This operation that creates a heap from an un-ordered collection of items stored in an array. We must start with a complete binary tree (an array with no empty elements except consecutively at the end of the array). 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 right to left 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.

Finding the first leaf's parent is easy, just take the index of the last item (none empty item) in the array, find it's parent index which is ((ChildIndex - 1) div 2) then perform the bubble down on this index and continue for each preceding index until we get to the root (index 0).

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.