Practice Exercises: Heaps¶

Exercise 1¶

What are the minimum and maximum numbers of elements in a heap of height $h$?

Exercise 2¶

Prove by induction that a heap with $n$ nodes has exactly $\lceil n/2 \rceil$ leaves.

Exercise 3¶

Use the following loop invariant to argue the correctness of HeapSort:

At the start of each iteration of the for loop of lines 2--5, the subarray $A[1..i]$ is a max-heap containing the $i$ smallest elements of $A[1..n]$, and the subarray $A[i+1..n]$ contains the $n-i$ largest elements of $A[1..n]$, sorted.

Exercise 4¶

Give an algorithm that -given a max-heap- outputs the second largest element in the heap. For full points your algorithm should run in $\Theta (1)$ time.

Exercise 5¶

(a) How do Left(i), Right(i), Parent(i), and all other operations change if we use an array starting at index 0?

(b) Implement a heap in Python using a list. Note that you can do this without (but also with) defining a class by defining operations manipulating a list.

In [ ]: