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

  • Context:
  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Algorithm
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
Sign up Log in
1 reply · 2K views
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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? :confused:
 
Last edited:

Discussion

Physics news on Phys.org
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)