Finding $m$ largest numbers from union of $k$ sorted lists $A_1, A_2, \ldots, A_k$

Question

We are given $k$ sorted lists $A_1, A_2, \ldots A_k$ with corresponding sizes $n_1, n_2, \ldots n_k$. How can one find $m$ largest elements (numbers) from union of lists $A_1, A_2, \ldots, A_k$? We can assume, that numbers don't duplicate in lists, but I don't think that this is necessary assumption. Algorithm should run in $\mathcal{O}(k + m\log k)$ time.

Answer 1

Create a $\min\{m,k\}$-node skip-list whose keys are the largest element of the $\min\{m,k\}$ lists of which has the highest element and it's values are pointers to each list. This takes $O(k+\min\{m,k\}\log k)$ time.

Now, for $m$ times:

• write down the list $A_i$ from which the largest key in the skip list comes from (follow the pointer in the value of the node).
• remove the largest element in the list (can be done in $O(\log k)$).
• and insert the next-largest element in $A_i$.

Overall time complexity $O(k+m\log k)$, and no assumption about duplicates is needed.

---

EDIT: If you are concerned about the skip-list creation in the $m=o(k)$ case in $O(k+m\log k)$, just think of inserting all nodes to a heap, then popping the $m$ largest ones and inserting them to a skip-list.