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.
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.
(a) How do Left(i), Right(i), Parent(i), and all other operations change if we use an array starting at index 1?
(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.