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

Question

do part a) only

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

1. Get the data for the heap

2. Call BuildingMaxHeap() function with the array of data and ‘size.

3. Send the maximum value of the heap to the end of the array sequence and pop it

4. Heapify the remaining sequence for 3 times

5. The element now is the 3rd largest number

6. Exit

COMPLEXITY

Calling heapify has O(log(n)) time

Removing the element has O(1) time.

Call extract 3 times extract max O(3log(n))

The

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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