Only do Part b) 2. [10 You are given a binary max-heap H and you will design the

Question

Only do Part b)

2. [10 You are given a binary max-heap H and you will design the following two algorithms with different requirements. For both algorithms you may assume that the size of H is at least 3, and that all elements in H have distinct values. (a) Design the EXTRACT-THIRD-LARGEST (H) algorithm which removes and returns the third largest element in H The worst-case runtime must be O(logn). Write the pseudocode of your algorithm and justify its correctness and worst-case runtime. (b) Design the GET-THIRD-LARGESTCH) algorithm which returns the third largest element in H without removing it. The worst-case time complexity of your algorithm must be as low as possible. Only the fastest possible algorithm will get full mark. Write the pseudocode of your algorithm and justify its correctness and worst-case runtime Note: For both designs you may use the following functions that we learned from the lecture as helper functions: BUBBLE-DOWN, EXTRACT-MAX, INCREASE-KEY and INSERT

Explanation / Answer

part b:

Use a second max-heap and fill it with k or k+1 values into it (breadth first traversal into the original one) then pop k elements and get the desired one.

I suppose this should be O(N+logN) = O(N)

there's no O(log n)-time algorithm.

algo:

but using a second max heap and filling it with 3 or 4largest values using breath first traversal you can get your desired answer.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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