Suppose that we have k heaps, with at most n elements in each. We wish to combin

Question

Suppose that we have k heaps, with at most n elements in each. We wish to combine these into a single heap. Each of the following sub-parts describes one approach to merging the heaps, and you are asked to derive the big O running time.

a) We create a new, empty heap H. For each of the k heaps hi , we repeatedly remove the highest priority element and insert it into H, until hi is empty. What is the worst-case big O running time?

b) We create a new, empty linked list L. For each of the k heaps hi , we repeatedly remove the highest priority element and insert it onto the beginning of L, until hi is empty. We then transfer the elements of L into an array, and heapify the array. What is the worst-case big O running time?

c) We create a new, empty linked list L. For each of the k heaps hi , we iterate over its internal array and insert each element onto the beginning of L. We then transfer the elements of L into an array, and heapify the array. What is the worst-case running time?

d) We group the k heaps into k/2 pairs, and apply the algorithm from part (c) on each pair, leaving k/2 heaps. We then repeat this process until we are left with a single heap. What is the worst-case running time?

Explanation / Answer

c)
heap from an array in (n)(n) time using the BuildHeap algorithm
merge the two arrays in (n)(n) time
takes O(n) time due to heapify.
so total it takes O(n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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