Yes... @Axoren 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 min heap for a $k$ -way merging.
@Axoren 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?
@evinda Yes, which is why we can assume that the amortized cost of accessing those lists by their $k$-value is $O(1)$, and indexing each of those lists is also $O(1)$.
But since it's pseudocode, you don't need to go into the low-level stuff too deeply.
@Axoren At my algorithm I haven't returned anything yet... But the algorithm should return a new list that contains the elements of all the k lists sorted...
"@Axoren 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?"
Let's start by turning this into pseudocode, then.
Everything you said in that sentence, is a statement in pseudocode.
Pseudocode doesn't follow a specific syntax or grammar
As long as its understood.
So, first thing you mentioned is create a $k$-sized heap.
Next, you go one at a time through each of the lists, and add the first element to the heap.
Once the heap is full, you take the root, which is going to be the first element of the output list.
@Axoren In order to create a k-sized heap, do we use the following function?
BUILD-HEAP(A)
heapsize := size(A);
for i := floor(heapsize/2) downto 1
do HEAPIFY(A, i);
end for
END
@Axoren But how can we put at the first position of a new list the root? Do we declare again a variable of the form LNEW and then add the element with this command: