K-way merge algorithm: Difference between revisions

Revision as of 16:23, 1 June 2017

Revision as of 02:27, 4 August 2017

Line 57:

Every leaf stores a pointer to one of the input arrays.

Every node stores a value and an index.

For the ki-th leaf the value is the value that its pointer points to and the index is ki.

For every internal leaf the value is the minimum of the values of the node's children.

The index of an internal leaf indicates which input array the value comes from.

Line 64:

It then updates the values of the nodes on the path from the corresponding leaf to the root.

As the tree is balanced, this path contains only Θ(log k) elements.

As there are n elements that need to be extracted, the resulting total running time is Θ(n log k).

===== Example =====