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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Why does it not work? $\endgroup$ – Raphael♦ Nov 19 '14 at 21:23
  • $\begingroup$ What do the arrows in the first line mean? $\endgroup$ – David Richerby Nov 19 '14 at 22:39
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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '14 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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