Homework 4

Download the corresponding ipynb file here: hw-4.ipynb.

Heaps

Exercise 1 (2 points) Justify why the height of heap with n nodes is \lfloor\lg{n}\rfloor.

Exercise 2 (3 points) Show that, with the array representation for storing an n-element heap, the leaves are the nodes indexed by \lfloor n/2 \rfloor,\lfloor n/2 \rfloor+1,\ldots, n-1.

Exercise 3 (3 points) For any index i into an array, print all the nodes at that level. You may either give an algorithm or its Python implementation.

Exercise 4 (2 points) Show that each child of the root of an n-node heap is the root of a subtree containing at most 2n/3 nodes.