Explore BrainMass

# Merging Sorted Lists Using Heaps

Not what you're looking for? Search our solutions OR ask your own Custom question.

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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.

https://brainmass.com/computer-science/sorting/merging-sorted-list-heaps-70665

#### Solution Preview

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 ...

#### Solution Summary

This solution assists in merging sorted lists using heaps.

\$2.49