MHB Merging $k$ Sorted Lists with a Thin Heap: A $\mathcal{O}(n \lg k)$ Algorithm

[evinda]

Hello! (Wave)

I am asked to write a $Ο (n \lg k)$ - time algorithm that merges $k$ sorted lists into one sorted list, where $n$ is the the total number of elements in all the input lists.
Hint: Use a thin heap for a $k$ -way merging.

Do you have an idea what could be meant with [m] thin heap [/m] ? (Worried)

Also, how could we merge $k$ sorted lists into one using a heap?

 

[evinda]

Finally, a min heap is meant...
So do we have to have a heap with $k$ positions, put the elements of the first positions of the $k$ lists in the heap, heapify and delete the root, which will be the smallest element, and put it into the new list, then place at the root the second element from the list from which the minimum was, then heapify and continue the same procedure? (Thinking)