Show that in any subtree of a max-hcap, the root of the subtree contains the lar

Question

Show that in any subtree of a max-hcap, the root of the subtree contains the largest value occurring anywhere in that subtree. Is the array with values (23, 17, 14, 6, 13, 10, 1, 5, 7, 12) a max-heap? Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = (5, 13, 2, 25, 7, 17, 20, 8, 4). What is the running time of quicksort when all elements of array A have the same value? The quicksort algorithm of Section 7.1 contains two recursive calls to itself. After quicksort calls Partition, it recursively sorts the left subarray and then it recursively sorts the right subarray. The second recursive call in quicksort is not really necessary; we can avoid it by using an iterative control structure. This technique, called tail recursion, is provided automatically by good compilers. Consider the following version of quicksort, which simulates tail recursion: taIl-RECURSIVE-quicksort(A, p, r) while p

Explanation / Answer

1. Base Case:

When k n / 2 +1, n , k is a leaf node of a max-heap since n / 2 is the index of the last parent, and the subtree rooted at k just contains one node. Thus, node k contains the largest value in that subtree.

Inductive Step:

Let k 1,n / 2 s.t. k is an internal node of a max-heap, and assume s.t. k < i n, P(i) is true. i.e. The node i of the subtree rooted at i contains the largest value occurring anywhere in that subtree. [inductive hypothesis] Now let us consider node k: 1. k's left child 2k and right child 2k + 1 contain the largest value of k's left and right subtree, respectively. (by the inductive hypothesis that for k < i n, P(i) is true) 2. k's value is larger than its left child 2k and right child 2k + 1. (by the max-heap property)

So, we can conclude that node k contains the largest value in the subtree rooted at k. Thus, by the principle of strong mathematical induction, P(k) is true for all nodes in a max-heap.

4. QUICKSORT will have to go through all the values in A. And since all values are the same, each recursive call will lead to unbalanced partitioning.

the recurrence will be:

T(n)=T(n1)+(n)T(n)=T(n1)+(n)

The above recurrence has the solution :

T(n)=(n2)T(n)=(n2)

Hence the running time of QUICKSORT in this case is

(n2)(n2).

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.