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.

Solution. Recall that a heap is a (almost complete) binary tree.

Let h be the height of the n-node heap. Since the result is true for h=0, we can assume that h\geq 1. Possibly except for the last level, each level has number of nodes twice the level above it. Consequently, the ith level has 2^i many nodes for any height level i=0,1,\ldots,h-1; note that we excluded the hth level.

So, the total number of elements in the tree excluding nodes in the height level (h) is the following geometric series: 2^0 + 2^1 + 2^2 + \ldots, 2^{h-1}=\frac{2^h-1}{2-1}=2^h-1. Now, we assume that the lowest level has x many elements, where 1\leq x\leq 2^h. Since we assume that the height of the tree is h, h cannot be 0. Also, x is exactly 2^h if the tree is complete.

Therefore, the total number of elements in the heap is n = (2^h-1)+x. \tag{1} In other words, h=\lg{(n-x+1)}.

In order to conclude that h=\lfloor\lg{n}\rfloor, we must show that h is an integer such that h\leq\lg{n} but h+1\geq\lg{n}.

We note the following:

  1. h=\lg{(n-x+1)}\leq\lg{n}. This is because x\geq1 and \lg is an increasing function.

  2. Since x\leq2^h, we get from (1) that n\leq(2^h-1)+2^h=2^{h+1}-1. So, h+1\geq\lg{(n+1)}\geq\lg{n}. The last inequality is due to the fact that \lg is an increasing function.

Therefore, h=\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.

Solution. It is enough to show that \lfloor n/2\rfloor is the index of the first leaf in the heap, since any node with a larger index must also be a leaf.

The result is already true if the height of the heap is 0. So, we can assume that the heap is non-trivial.

We now note that the node previous to the first leaf must be the parent of the last leaf, which has index n-1. Recall that the index of the parent of a node i is \lfloor (i-1)/2 \rfloor. Therefore, the index of the first leaf is: \lfloor (n-2)/2 \rfloor + 1=\lfloor n/2 \rfloor.

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.

Solution. 

def heap_level(heap, target):

  first = 2 ** target - 1
  max = 2 ** (target + 1) - 2
  last = min(max, len(heap) - 1)
    
  if first > len(heap) - 1:
    raise ValueError("The level exceeds the heap's boundary.")

  for idx, value in enumerate(heap[first:last + 1], start=first):
    print(value, end=' ')
  print("")

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.

Solution. Let h be the height of the heap and n the total number of nodes. Without any loss of generality, we assume that h\geq1 i.e., the heap is non-trivial.

Let x be the number of nodes on the last level. Since this is the h-th level, we have 1\leq x\leq 2^h. Also, from Equation (1): n=2^h-1+x.

We denote by L and R the number of nodes in the left and right subtrees below the root, respectively.

L: Since the height of the left subtree is h-1 with at most x many nodes on the last level, we must have: L\leq2^{h-1}-1+x So, the ratio is \frac{L}{n}\leq\frac{2^{h-1}-1+x}{2^h-1+x}=\frac{1+\frac{x-1}{2^{h-1}}}{2+\frac{x-1}{2^{h-1}}}=\frac{1+\xi}{2+\xi}=f(\xi), where \xi=\frac{x-1}{2^{h-1}}. So, 1\leq x\leq 2^h implies that 0\leq\xi\leq1. Note that f(\xi) is an increasing function of \xi, so the ratio L/n attains its maximum when \xi\to1 (equivalently h\to\infty), with the maximum value approaching 2/3. Therefore, L/n\leq2/3.

R: The argument is similar to L.