We saw an algorithm for making a heap (slow-make-heap) that we described as \"ra

Question

We saw an algorithm for making a heap (slow-make-heap) that we described as "rather inefficient". Analyse the worst case for this algorithm, and compare it to the linear-time algorithm make-heap. In Section 5.7 we saw an algorithm for making a heap (slow-make-heap) that we described as "rather inefficient". Analyse the worst case for this algorithm, and compare it to the linear-time algorithm make-heap. procedure slow-make-heap(T[1.. n]) {This procedure makes the array T [1.. n] into a heap, albeit rather inefficiently} for i - 2 to n do {percolate} (T[1 ..i], i) procedure slow-make-heap(T[1.. n]) {This procedure makes the array T [1.. n] into a heap, albeit rather inefficiently} for i - 2 to n do {percolate} (T[1 ..i], i) procedure sift-down(T[1.. n], i) {This procedure sifts node i down so as to re-establish the heap property in T[1 .. n]. We suppose that T would be a heap if T[i] were sufficiently large. We also suppose that 1 lessthanorequalto i lessthanorequalto n.} k - i repeat j - k {find the larger child of node j} if 2j lessthanorequalto n and T[2j] > T[k] then k - 2j if 2j T[k] then k - 2j + 1 exchange T[j] and T[k] {if j = k, then the node has arrived at its final position} until j = k procedure percolate(T[1 .. n], i) {This procedure percolates node i so as to re-establish the heap property in T[1.. n]. We suppose that T would be a heap if T[i] were sufficiently small. We also suppose that 1 lessthanorequalto i lessthanorequalto n. The parameter n is not used here.} k - i repeat j - k if j > 1 and T[j divide 2]

Explanation / Answer

In slow make heap we need to call percolate mathod n times and the runtime of perlocate is log n

worst case run time of percolate is log n

So worst case run time of slow make heap is O(nlogn) where as make heap method tahes only O(n)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

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