When we have two sorted lists of numbers in non-descending order, and we need to merge them into one sorted list, we can simply compare the first two elements of the lists, extract the smaller one and attach it to the end of the new list, and repeat until one of the two original lists become empty, then we attach the remaining numbers to the end of the new list and it's done. This takes linear time. Now, try to give an algorithm using O(n log k) time to merge k sorted lists (you can also assume that they contain numbers in non-descending order) into one sorted list, where n is the total number of elements in all the input lists. Use a binary heap for k- way merging.

Question

contestada

Respuesta :

mirianmoses mirianmoses · Answer 1 · 2020-02-13T16:12:48+01:00

Answer:

Explanation:

Firstly of all we have to construct the min-heap of the k-sub list and each sub list which is a node in the constructed min-heap.

We have several steps to follows:

Step-1. When we compare the two sub lists, at the starting we can compare their first elements which is actually their minimum elements.

Step-2. The min-heap formation will cost be O(k) time.

Step-3. After the step 1 & step 2 we can run the minimum algorithm which can be extracted from the minimum element in the root list.

Step-4. Then Update the root list in the heap and after that simplify the min-heap as maintained by the new minimum element in the root list.

Step-5. If any root sub-list becomes empty in the step 4 then we can take any leaf sub-list from the root and simplify it.

Step-6. At every Extraction of the element it can take up to O(log k) time.

Hence, We can say that the extract of n element in the total whose

Running time will be O(n log k + k) which can be equal to the O(n log k+ k) (since k < n).