How to Form a Sequence in a Heap
Practice: Heaps (with solutions)¶
Difficulty assessment:
(*) Basic. You should be able to easily do this.
(**) Standard. Core material to test your understanding.
(***) Advanced. Possibly slightly above the level of the assignments.
Exercise 1 ( * ):
(a) Give the definition of a max-heap.
Solution:
A max-heap is a nearly complete binary tree, filled on all levels except possibly the lowest, with the lowest level filled from left to right, that satisfies the max-heap property: for every node $i$ other than the root $key[Parent(i)] \ge key[i]$.
(b) Is the sequence $\langle 24, 16, 21, 6, 8, 19, 20, 5, 7, 4\rangle$ a max-heap?
Solution:
No, it is not. $key[8] = 7 > 6 = key[(8-1)//2] = key[Parent(i)]$ violates the max-heap property.
Note: The above is sufficient as answer, but you could also illustrate this by a figure as given below.
(c) We can store a max-heap in an array. Argue that the $k$-th node on level $j$ of a max-heap is stored at position $2^j + k - 2$. (E.g., the $1$st node on level $0$ is the root, which is stored at position $2^0 + 1 - 2 = 0$.)
Solution:
A heap, when stored in an array, is stored level by level, from left to right. The root occupies the first cell of the array A[0]. The left child of the root occupies A[1], and the right child of the root occupies A[2].
Level 0 contains 1 node (the root), level 1 contains 2 nodes, level 3 contains 4 nodes, and so on. So, level $i$ contains $2^i$ nodes. Level 0 to level $j-1$ together contain $\sum_{i=0}^{j-1} 2^i = 2^j - 1$ nodes. (Note: a geometric sum.)
Thus, the first node of the $j$th level will occupy $A[2^j - 1]$ (since it is the $2^j$-th node, and we start with index 0), the $k$-th node on level $j$ will occupy $A[2^j - 1 + (k-1)]=A[2^j + k - 2]$ (since it comes $k-1$ positions after the $1$st node of level $j$).
Exercise 2 ( ** ):
Demonstrate the execution of HeapSort on the following input: $\langle 7, 14, 9, 12, 25, 41, 2 \rangle$. Show every step that changes the array. (One call of Max-Heapify counts as one step.) It is sufficient to note the operation and write the array after each step, i.e., you do not need to draw the heap as tree.
Solution:
(Note: It might be helpful, when solving the exercise, to actually draw the heaps.)
Input: $[7, 14, 9, 12, 25, 41, 2]$
We start with the Build-Heap phase.
Max-Heapify(A, 2): [7, 14, 41, 12, 25, 9, 2]
Max-Heapify(A, 1): [7, 25, 41, 12, 14, 9, 2]
Max-Heapify(A, 0): [41, 25, 9, 12, 14, 7, 2]
Now we do the actual sorting.
Swap 2 and 41 and Max-Heapify(A, 0): [25, 14, 9, 12, 2, 7, 41] (Note: The sorted part is shown in bold.)
Swap 7 and 25 and Max-Heapify(A, 0): [14, 12, 9, 7, 2, 25, 41]
Swap 2 and 14 and Max-Heapify(A, 0): [12, 7, 9, 2, 14, 25, 41]
Swap 2 and 12 and Max-Heapify(A, 0): [9, 7, 2, 12, 14, 25, 41]
Swap 2 and 9 and Max-Heapify(A, 0): [7, 2, 9, 12, 14, 25, 41]
Swap 2 and 7 (and Max-Heapify(A, 0)): [2, 7, 9, 12, 14, 25, 41]
Exercise 3 ( ** )::
Describe a linear-time algorithm MaxHeapVerify($A$) that checks whether a given array $A$ is a max-heap. Prove its correctness using the loop invariant, and analyze the running time. (Note: You can also give a recursive algorithm. Then prove correctness using strong induction.)
Solution:
To verify if a given array is a max-heap, we need to check whether each node satisfies the max-heap property, that is, that $key[Parent(i)] \ge key[i]$ for all nodes $i$ except for the root. In a max-heap, the parent of node $i$ is stored at the position $(i-1)//2$. Thus, we can linearly scan the array from right to left and test for each node whether the max-heap property is satisfied.
In the following code, we assume that $A$ stores the keys directly
1 def MaxHeapVerify ( A ): 2 for i in range ( len ( A ) - 1 , 0 , - 1 ): 3 if A [( i - 1 ) // 2 ] < A [ i ]: return False 4 return True
We will prove the correctness of the algorithm using the following loop invariant:
Loop Invariant: at the start of iteration $i$ for each element in $A[i + 1: len(A)]$ the key of the parent of the element is larger or equal than the key of the element itself.
Initialization: At the start we have $i = len(A)-1$ and the subarray $A[len(A)-1:len(A)-1]$ is empty. Thus the loop invariant holds.
Maintenance: Assume the loop invariant holds at the start of iteration $i$. Then for each element in $A[i + 1: len(A)]$ the key of the parent of the element is larger or equal than the key of the element itself. We need to prove that the loop invariant also holds at the start of the next iteration.
Within an iteration we check if the key of the parent of the element $A[i]$ is greater or equal to the key of $A[i]$. If it does not hold then the algorithm terminates and reports false. Trivially this is correct as at least for one element the max-heap property does not hold. If the algorithm does not terminate, then the key of the parent of $A[i]$ is larger or equal than the key of $A[i]$ itself. Combining this with the our initial observation by the LI we get that for each element in $A[i : len(A)]$ the key of the parent of the element is larger or equal than the key of the element itself. Thus, at the start of the next iteration (with $i-1$) indeed the LI holds.
Termination: The loop terminates when $i > 0$ no longer holds, so $i = 0$. Combining this with the loop invariant we get that for each element in $A[1:len(A)]$ the key of the parent of the element is larger or equal than the key of the element itself. Thus, the max-heap property holds for all the non-root nodes of the heap. Thus the algorithm correctly returns true in this case.
Running time: Each line of the algorithm takes $O(1)$ time, and the loop makes $n-1$ iterations. Thus, the total running time of the algorithm is $O(n)$.
How to Form a Sequence in a Heap
Source: https://www.win.tue.nl/~kbuchin/teaching/JBP030/notebooks/P-heaps-sol.html