Heap Overview

• 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/vector. The root of the tree has index one (the vector 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/vector

Questions About Heaps

1. Where is the smallest element in a heap (and why?)

2. Where is the largest element in a heap (and why?)

3. Where is the parent of the element with index 11 when a heap is stored in a vector?

4. Where is the parent of the element with index k when a heap is stored in a vector?

5. If the value 19 in the heap above is changed to 25, is the heap property maintained?

6. If the value 21 in the heap above is changed to 13, is the heap property maintained?

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

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 shonw above on the right.

The 12 belongs as the childe 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

1. 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?

2. Draw the heap that results from adding 12, 7, 11, 9, 15, 10, 8 in that order to an initially empty heap.

3. What binary search tree also a heap?

4. Part of the declaration for a class IntHeap for storing integers might be as shown on the left, the constructor (from intheap.cpp) is shown on the right. The constructor inserts a dummy value into the location with index zero since the root of a heap in our use has index one.

   class IntHeap { public: IntHeap(); void insert(int elt); int getmin() const; private: tvector<int> myList; };

   IntHeap::IntHeap() // post: heap has zero elements { myList.push_back(0); }

   The IntHeap::insert function is started below, fill in the loop test and the loop body so that it works as described in this writeup.

   void IntHeap::insert(int elt) { myList.push_back(elt); // add to end, maintain heap shape int loc = myList.size(); // where new element goes int parent = loc/2; // parent of new element while( ) { } myList[loc] = elt; // where new element really goes }