Q. There are k sorted lists and we have to merge them to make a single sorted list in best time.

A. I used min heap of size k to contain one element of each list. Each node of heap also contains the id of the list it belongs to.

- Pick out first element of each list and push it into heap.
- Take the minimum element out of the heap. Record the list it belongs to say list j.
- Push the next element from list j back into heap.
- Repeat the operation till all elements are parsed.

If all lists are of length n, each element has to pushed into heap at some point.

Complexity for pushing the element is logk in heap.

Overall complexity will be O(nk logk).

Advertisements