I need help figuring out an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists.
I believe we are supposed to use a Heap for k-way merging.© BrainMass Inc. brainmass.com December 24, 2021, 5:47 pm ad1c9bdddf
Yes, you can do it with (binary) heaping in O(n log k) time
I assume that you have some familiarity with heaps and/or access to appropriate books or notes.
For definiteness, let us use a Min-Heap.
We need here to recall only the following 3 properties of heaps:
- A Heap is a nearly complete binary tree and, given k items, they can be arranged into a Heap in a O(k log k ) time.
- If the root of a Heap is replaced by a new item, the whole structure can be "heapified", that is the new item can trickle down to such a node as to make the tree a heap again, in O(log k) time.
- The root of a Min-Heap is the minimum of all its elements
Now let ...
This solution assists in merging sorted lists using heaps.