You could use binary heap, so the compexity is O(n log k) and you get
the final list immediatly.
First you put into heap first elements of the streams. Than you repeat
the following step:
extract minimal element from heap, add it to output stream and add next
element from the stream to which
On 1/18/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Given k sorted streams where each stream could possibly be infinite in
length, describe an efficient algorithm to merge the k streams into a
new stream (also in sorted order).
// assuming that you sort from the lowest to the highest value
For the question 2,
What to do you mean by Inverting tree? Are you talking of the mirror image.
If so you dont have to make two recursive calls. You can call only for left child recusively.
And since this is a tail recursion ,you can convert into a iterative solution easily.
I dont think any
Hey Mattia,
Say n is the total number of elements in all the streams put together.
The time complexity of your solution is O(n * k). Since you see every
element once and k-1 comparisons are required in the worst case to find
the smallest element.
This approach is actually fine if the streams
