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.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...

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] ...