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

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

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.

(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 [ ]:

```
```