Question 4 continued! values from the binary min heap, into an initially-empty a

Question

Question 4 continued! values from the binary min heap, into an initially-empty array of the same siz array should be sorted values from low to high. Describe an approach to write an algorithm or pseudo-code. Just describe your approach/algorithm in s/values. You want to move the The final co contents of do this task. You do not need to (d) [5 pts] What is the run-t give the tightest possi ime complexity of your approach in part (c)? Please use the Big-O notation and ible upper bound for the worst-case running time of your algorithm.

Explanation / Answer

1) extract min operation: This operation removes the minimum value in min-heap By first swapping the root element to end of the tree Then removes the element at end of the tree Then Pushes root element down until it satisfies min-heap property Perform extract-min operation n times, and store these n-items in array 2) Extract-min operation takes O(log(n)) time so, doing extract-min operation n-times takes O(n log(n)) time complexity

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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