Compsci 100e, Heap Questions

Name: __________________________   NetID: _____________

Name: __________________________   NetID: _____________

Name: __________________________   NetID: _____________

Heaps

A binary heap is a method of storing a binary tree in an array when the binary tree maintains two properties:

The heap shape: the binary tree must be a complete tree, that is every level of the tree is full/complete except perhaps for the last level which is filled in from left to right.

The heap property: every node is smaller than its two children.

The tree shown below on the left has both the heap shape and the heap property.

Binary trees that are heaps are typically stored in an array. The root of the tree has index one (the array element with index zero isn't used). The children of the root are at indexes two (left child) and three (right child). In general, the children of the tree node with index k have indexes 2k (left child) and 2k+1 (right child).

The binary tree on the left below is stored in a vector as shown on the right.

Conceptual Heap Heap in array

Questions About Heaps

Where is the smallest element in a heap (and why?)
Where is the largest element in a heap (and why?)
Where is the parent of the element with index 11 when a heap is stored in an array ?
Where is the parent of the element with index k when a heap is stored in an array?
If the value 19 in the heap above is changed to 25, is the heap property maintained?
If the value 21 in the heap above is changed to 13, is the heap property maintained?
If a new node with 19 is added as the left child of 17 in the heap above, is the heap shape maintained?

Adding an element to a Heap

When a new element is added to a heap, both the heap shape and the heap property must be maintained. To maintain the shape, the new element must be added as the last element of the array (why?). This may violate the heap property, so all nodes on the path from the root to the newly added leaf must be checked to see where the new value really belongs, starting from the leaf.

This process is shown below for adding the value 12 to the heap shown above.

First, the 12 is shown on the left added to maintain the heap shape. However, the 12 doesn't belong there (the heap property is violated) so the yellow node is shown on the right with no value, the newly added value 12 is "waiting" to find its place as all nodes on the path from the newly added leaf to the root are examined to find where the 12 belongs.

In the diagram above on the right, the 12 can't stay as a leaf, so the value in node above it is moved down to the leaf, and the yellow node conceptually moves up -- this is a new tentative spot for the 12 as shown on the left below.

The 12 cannot stay in the location shown above on the left since it is less than 15. The 15 is moved down to the yellow node, and the yellow node conceptually moves up -- this is the tentative spot for the 12 as shown above on the right.

The 12 belongs as the child of 7 (the root) since it is less than the root. The final tree is shown below. The newly-added 12 has been moved up from its original tentative location as a leaf (where the 21 is below) to its final location.

Questions About Adding Values to a Heap

Suppose new values are added to the last heap above (with 10 elements, the root is 7 that has both children with the value 12).
1. If a new value of 20 is added what value is the parent of the 20 node?
2. If after adding 20 the value 10 is added what are the values that are children of the root?
3. What new values would end up at the root?
Draw the heap that results from adding 12, 7, 11, 9, 15, 10, 8 in that order to an initially empty heap.
Given the heap you drew for previous problem, draw the heap that results if you remove the smallest element and keep the heap properties.
Where is the largest element in a min-heap? What is the big-Oh complexity of finding the largest element in the heap? Justify your answer.

Jeffrey R.N. Forbes

Last modified: Wed Nov 18 15:12:12 EST 2009