Heap Specification

Definition

A heap is a complete binary tree, whose entries satisfy the heap ordering property.

The heap ordering property states that the parent always precedes the children. There is no precedence required between the children. The precedence must be an order realtionship. That is, we must be able to determine the precedence between any two objects that can be placed in the heap, and this precedence must be transitive. Consequently the root node will precede all other nodes in the heap as long as the heap ordering property is maintained.

A heap is a complete binary tree. This means that visually nodes are added to the binary tree from top-to-bottom, and left-to-right. More formally this means that we can arrange the nodes in a contiguous array (indexed from 0) using the following formulas for determining the parent-child relationships.

• left child = 2 * parent + 1
• right child = 2 * parent + 2
• parent = floor( (child-1) / 2)

For example, if we have a heap containing 6 nodes, the last node would be node 5. Its parent would be node 2, and it would be the left child of its parent. Furthermore, its parent, node 2, would be the right child of the root node, node 0.

Key Property

Since the heap is a complete binary tree, we can count the nodes in each level.

• Level 0 contains the root node.
• Level 1 contains the children of the root node.
• Level L contains the children of the nodes in Level L-1.

Note that if the binary tree is complete and there is a node in level L, then each preceding level must contain all the possible nodes for that level. Consequently, a tree with L levels will have N nodes where

2^0 + 2^1 + . . . + 2^(L-1) + 1 = 2^L <= N <= 2^0 + 2^1 + . . . + 2^L = 2^(L+1) - 1

Turning this around we can conclude that

L <= log(N) < L+1

where log means the log base 2.

This meas that the longest branch from the root to any leaf contains at most log(N) nodes. In turn this means that the complexity of any algorithm which only accesses nodes on a single branch will be O(log(N)).

Growing a heap

A heap can be grown by

1. Adding a node with the new value at the next possible position that maintains the tree as a complete binary tree,
2. Comparing the new node with its parent node and exchanging the nodes whenever the new node precedes the parent, and
3. Repeating this last step until the new node reaches a position where its parent precedes it or when it becomes the root.

At the end of the preceding steps the heap has grown with the addition of one node and the heap property has been maintained. This process is sometimes described as the bubble up phase.

The Heap Growth Example illustrates in detail what happens when we start with an empty heap and adds the letters F, E, D, C, B, and A in that order.

Removing items from a heap in order

The root always contains a node that precedes all the other nodes in the heap. We want to remove that root node and repair the collection so that it satisfies the definition and properties of a heap.

1. Remove the root node and replace it with the last node. The heap is now a complete binary tree with N-1 nodes. Refer to the root node as the parent node.
2. Compare the parent node with its children. If necessary, exchange the parent with the child that will maintain the heap ordering property.
3. Repeat this last step until the parent node reaches a position where it precedes all of its children or where it becomes a leaf.

At the end of the preceding steps the node which precedes all the other nodes in the heap has been removed and the heap property has been maintained. This process is sometimes described as the sifting down phase.

The Heap Delete Example illustrates in detail what happens when we start with the heap from the previous example and remove the letters A, B, C, D, E, and F. Note that this is the order that the letters will be removed because the precedence used in the previous example was alphabetical order.

Priority Queue

The algorithms for adding and item to a heap and for removing the item that precedes all other items each work on a single branch of the binary tree and for a heap with N nodes each algorithm is O(log(N)) operations. Thus we have defined O(log(N)) enqueue and dequeue methods for a priority queue. Priority queues can be used for a number of tasks. We will explore the use of a priority queue as the key component in implementing a discrete event simulation.

Heapsort

By inserting N items into a heap and then removing them, we have defined a sorting algorithm whose worst case perfomance is O(N*log(N)). It has been shown that this Heapsort algorithm has the best worst case performance of any sorting algorithm.