HEAP SORT(A) 02 BUILD-MAX-HEAP(A) for i = A middot length downto 2 exchange A [1

Question

HEAP SORT(A) 02 BUILD-MAX-HEAP(A) for i = A middot length downto 2 exchange A [1] an A[i] A middot heapSize = A middot heapSize - 1 MAX-HEAPIFY (A, 1) BUILD-MAX-HEAP(A) A heapsize = A middot length for i = floor (A middot length/2) down to 1 MAX-HEAPIFY (A, i) MAX-HEAPIFY (A, i) L = 2*i R = 2*i + 1 if L A[i] largest = L else largest = i if R A[largest] largest = R if largest! = i exchangeA[i] and A[largest] MAX-HEAPIFY (A, largest) Suppose we apply HEAPSORT (as shown in the pseudocode on the preceding page) to an array A which has the following initial contents: Exactly how many times is the assignment L = 2*i on line 12 executed during the sort? L=2*i is executed exactly ______ times.

Explanation / Answer

In heap sort algorithm a heap of unsorted array is created first. Then the array is sorted by removing the largest or smallest from heap and it is inserted in sorted array.

There are 7 array elements. So, first is compared with 6 and next is by 5 and so on up to last element.

So the line 12 is called 6 + 5 + 4 + 3 + 2 + 1 = 21

Hence the answer is 21

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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