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 singleheap. Each of the following sub-parts describes one approach to merging the heaps, and you are asked toderive the bigOrunning time. you must provide an explanation for your answer.

a) We create a new, empty heap H. For each of thekheapshi, we repeatedly remove the highest priorityelement and insert it into H, untilhiis empty. What is the worst-case bigOrunning time?

b) We create a new, empty linked list L. For each of the k heaps hi, we repeatedly remove the highest priorityelement 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 bigOrunning 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

Number of heaps = k

Number of elements in each heap = n

Time complexity to create a single heap by using k heaps =   O(k × n)

a) Time complexity of removing each element from heap = O(log n)

Total time complexity of removal n×k elements from the original heap = n × k O(log n)

Time complexity to insert the deleted node in new heap = O(log n×k)

Time complexity to insert n×k elements in the new heap = n×k×O(log n×k)  

Thus, overall time complexity of creating new heap = (n×k× O(log n))+(n×k×O(log n×k)

                                                                                    = O(n×k×log n)

b) Time complexity of removing each element from heap = O(log n)

Total time complexity of removal n×k elements from the original heap = n × k O(log n)

Time complexity to insert the deleted node in Linked List L = O(1)

Time complexity to insert n×k elements in the Linked List L = n×k×O(1)  

Time complexity of insertion in a Linked List is constant. Thus, it will not be included.

Time complexity to insert n×k elements in a heap and heapify the heap = O(n ×k)

Thus, overall time complexity of creating heap from array = (n×k× O(log n))+(O(n×k))

                                                                                              = O(n×k log n)

c) Time complexity to insert n×k elements in the Linked List L from the heap = O(n×k)  

Time complexity to insert n×k elements in a heap and heapify the heap = O(n ×k)

Thus, overall time complexity of creating heap from array = (O(n×k))+(O(n×k))

                                                                                              = O(n×k)

d) Divide k heaps into k/2 heaps. Means k heaps shrink to k/2 number of heaps.

From the problem, it can be understood that it is asked to use part c) algorithm. Complexity in part c) is O(n × k), use it further.

Time complexity to shrink k heaps into k/2 heaps = O(2n) ×( k/2)

Time complexity to shrink k/2 heaps into k/4 heaps = O(4n) × (k/4)

Thus, overall total time complexity = O(2n) ×( k/2) + O(4n) × (k/4) + … + O(n × k)

                                                         = O(n × k × log k)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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