Software Developer

6.3-2 Why do we want the loop index $i$ in line 2 of BUILD-MAX-HEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from to $\lfloor A.length/2 \rfloor$? Otherwise we won't be allowed to call MAX-HEAPIFY, since it will fail the condition of having the subtrees be max-heaps. That is, if we start with 1, there is no guarantee that A[2] and A[3] are roots of max-heaps. 6.3-3 Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element heap. The height of binary heap is as following: A heap of size $n$ has at most $\lceil n/2^{h+1} \rceil$ nodes with height $h$. Key Observation : For any $n > 0$, the number of leaves of nearly complete binary tree is $\lceil n/2 \rceil$. Proof by induction Base case : Show that it's true for $h = 0$. This is the direct result from above observation. Inductive step : Suppose it's ture for $h - 1$. Let $N_h$ be the number of nodes at height $h$ in the n-node tree $T$. Consider the tre

 6.2-2 Staring with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY? MIN-HEAPIFY(A, i) l = LEFT(i) r = RIGHT(i) if l ≤ A.heap-size and A[l] < A[i] smallest = l else smallest = i if r ≤ A.heap-size and A[r] < A[smallest] smallest = r if smallest != i exchange A[i] with A[smallest] MIN-HEAPIFY(A, smallest) The running time is the same. Actually, the algorithm is the same with the exceptions of two comparisons and some names. 6.2-5 The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an interative control construct (a loop) instead of recursion. MAX-HEAPIFY(A, i) while true l = LEFT(i) r = RIGHT(i)

6.1-1  What are the minimum and maximum numbers of elements in a heap of height h? At least $2^h$ and at most $2^{h+1}-1$. Can be seen because a complete binary tree of depth $h-1$ has $\Sigma_{i=0}^{h-1}2^i = 2^h -1$ elements, and the number of elements in a heap of depth is $h$ between the number for a complete binary tree of depth $h-1$ exclusive and the number in a complete binary tree of depth $h$ inclusive. 6.1-2 Show that an n-element heap has height $\lfloor lgn \rfloor$. Write $n = 2^m - 1 + k$ where $m$ is as large as possible. Then the heap consists of a complete binary tree of height $m-1$, along with $k$ additional leaves along the bottom. The height of the root is the length of the longest simple path to one of these k leaves, which must have length $m$. It is clear from the way we defined $m$ that $m=\lfloor lgn \rfloor$. 6.1-3 Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring anywhere in that subtree. If the largest ele

6.1 Heaps The (binary) heap data structure is an array object. An array A that represents a heap is an object with two attributes: A. length , which (as usual) gives the number of elements in the array, and A. heap-size , which represents how many elements in the heap are stored within array A. That is, although A[1..A. length ] may contain numbers, only the elements in A[1..A. heap-size ], where 0 $\leqslant$ A. heap-size  $\leqslant$ A. length , are valid elements of the heap. The root of the tree is A[1], and given the index i of a node, we can easily compute the indices of its parent, left child, and right child:   PARENT(i) return [i/2] LEFT(i) return 2i RIGHT(i) return 2i + 1 6.2 Maintaining the heap property MAX-HEAPIFY(A, i) l = LEFT(i) r = RIGHT (i) if l <= A.heap-size and A[l] > A[i] largest = l else largest = i if r <= A.heap-size and A[r] > A[largest] largest = r if largest != i exchange A[i] with A[largest] MAX-HEAPIFY(