3
$\begingroup$

We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$.

How can we get the $m$ greatest elements in running time $O(k + m\lg k)$?

I have tried to use MIN-HEAP size of $k$ since we have $k$ arrays. I have to navigate through the ends of the $k$ array somehow. By extracting the min of heap and getting new element from respective array was my idea but it does not work. I could not figure out getting m greatest elements.

$\endgroup$
2
  • $\begingroup$ Why does it not work? $\endgroup$
    – Raphael
    Nov 19, 2014 at 21:23
  • $\begingroup$ What do the arrows in the first line mean? $\endgroup$ Nov 19, 2014 at 22:39

1 Answer 1

2
$\begingroup$

Your idea works out. The idea is to maintain a heap of size $k$ which contains exactly one element from each array. For each array $A_i$, we maintain an index $p_i$ which keeps track of the position of the current element in the array. Initially, $p_i = n_i$, and we insert $A_i[n_i]$ into the heap. We then repeat the following $m$ times:

  1. Extract the maximum element from the heap.
  2. If the extracted element belonged to $A_i$, then we decrease $p_i$ by one and insert $A_i[p_i]$ into the heap.

The initialization phase takes time $O(k)$, and the extraction phase takes time $O(m\log k)$, for a total of $O(k+m\log k)$. You can prove that the extracted elements are indeed the $m$ largest ones.

$\endgroup$
1
  • $\begingroup$ Since we can build a max-heap of $k$ elements in $O(k)$ time, the preprocessing is in $O(k)$ and the condition on $m$ is obsolete. $\endgroup$
    – Raphael
    Nov 19, 2014 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.