8
$\begingroup$

Input: A set of $\ell$ arrays $A_i$ (of numbers).
The elements within each array are in sorted order, but the set of arrays is not necessarily sorted. The arrays are not necessarily the same size. The total number of elements is $n$.

Output: The $k$th smallest element out of all elements in the input.

What's the most efficient algorithm for this problem?

Is it possible, for example to achieve a running time of $O(\ell + \log n)$?

Improve this question
$\endgroup$
  • $\begingroup$ There's a very closely related question on SO, with unsatisfactory answers. $\endgroup$ – Joe Feb 4 '13 at 23:57
  • $\begingroup$ Are all the arrays of the same length? $\endgroup$ – vonbrand Feb 5 '13 at 0:15
  • $\begingroup$ The arrays are not necessarily the same size. However, I'm also interested in a special case where the sizes are geometric, that is array $A_i$ has size $n / 2^i$, but I doubt it will help in the running time. $\endgroup$ – Joe Feb 5 '13 at 0:21
  • 4
    $\begingroup$ How do you get $O(\ell\log n)$? You can get $O(\ell(\log n)^2)$ by emulating the "quickselect" algorithm. In each phase, you pick a pivot and calculate how many elements are below it, in $O(\ell\log n)$. Then you remove elements on the wrong side, and repeat. The process ends after $\log n$ iterations (in expectation, or in the worst case if you choose the pivot smartly). $\endgroup$ – Yuval Filmus Feb 5 '13 at 0:28
  • 2
    $\begingroup$ @Joe I think you should describe your algorithm too. It would be very interesting, and may provide a starting point for better algorithms if correct. If incorrect, people may be able to find any errors. $\endgroup$ – Paresh Feb 5 '13 at 9:08
5
$\begingroup$

You can do it in $O(l + k \text{ log } l)$ time and $O(l)$ extra space as follows:

  1. Build a binary heap with one entry for each of the arrays. The key for entry $i$ is the smallest element in array $A_i$. This takes $O(l)$ time.
  2. Select the smallest entry from the heap and remove it (taking $O(\text{log } l$) time). Add that entry back to the heap using the next smallest entry in the relevant array as its key (again $O(\text{log } l)$ time).
  3. Do the previous step $k$ times. The last element you remove from the heap is your answer.

If you replace the binary heap with a Fibonacci heap, I think this gets you down to amortized $O(l + k)$ time, but in practice it'll be slower than the binary heap unless $l$ is HUGE.

I suspect that the Fibonacci heap bound is optimal, because intuitively you're going to have to inspect at least $k$ elements to find the $k$th smallest one, and you're going to have to inspect at least one element from each of the $l$ arrays since you don't know how they're sorted, which immediately gives a lower bound of $\Omega(\text{max}(k, l)) = \Omega(k + l)$.

Improve this answer
$\endgroup$
  • 3
    $\begingroup$ You don't have to inspect at least $k$ elements since the arrays are sorted. See the solution in my comment, which gives $O(\ell (\log n)^2)$. $\endgroup$ – Yuval Filmus Feb 5 '13 at 14:34
  • 1
    $\begingroup$ You may improve the worst case running time in the RAM model, since you may implement your priority queue for $n$ elements in $o(\log n)$. In this model, you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n})$ and $\mathcal{O}(1)$ time for the findMin operation. $\endgroup$ – Massimo Cafaro Feb 5 '13 at 14:40
  • 1
    $\begingroup$ Are you sure the Fibonnaci heap supports the right operation? I think you're thinking of decrease-key in a min-heap. $\endgroup$ – Joe Feb 6 '13 at 0:57
  • $\begingroup$ This is basically the same as vonbrand's answer, with the added observation that you don't have to merge any elements after the kth one. $\endgroup$ – Joe Feb 6 '13 at 1:32
  • $\begingroup$ I believe Fibonacci heap allows you to decrease or increase a key in $O(1)$ time. Yes, this is basically the same answer, but observing that you only need to merge $k$ elements brings your runtime down a fair way. $\endgroup$ – Matt Lewis Feb 6 '13 at 11:57
5
$\begingroup$

Here is a randomized $O(\ell\log^2 n)$ algorithm. It can probably be derandomized using the same trick used to derandomize the usual quickselect.

We emulate the classical quickselect algorithm. In each phase, you pick a pivot and calculate how many elements are below it, in $O(\ell\log n)$, using binary search in each list. Then you remove elements on the wrong side, and repeat. The process ends after $\log n$ iterations in expectation.

Improve this answer
$\endgroup$
1
$\begingroup$

This seems to be resolved by the paper Generalized selection and ranking (Preliminary Version) by Frederickson and Johnson in STOC '80.

They give upper and lower bounds of: $\Theta(\ell + \sum_{i=1}^\ell \log|A_i|)$ which turns out to be $\ell \log n$ for most array size distributions.

The actual algorithm to achieve the upper bound is apparently given in a previous paper: Optimal algorithms for generating quantile information in X+Y and matrices with sorted columns, Proc. 13th Annual Conference on Information Science and Systems, The Johns Hopkins University (1979) 47-52.

Improve this answer
$\endgroup$
0
$\begingroup$

An $\ell$-way merge takes time $\Theta(n \log \ell)$ (use an efficient way to represent a priority queue of the head elements in each list), then you pick the $k$-th element in constant time. I think this is discussed in Knuth's "Sorting and searching" for sorting. Getting the smallest (or largest) clearly takes $\Theta(\ell)$, for an unsorted array it is $O(n)$ IIRC.

Please describe your algorithm.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ This is way slower than I'm interested in. You can find the median in $O(n)$ time just concatenating the lists and using the linear time selection algorithm. $\endgroup$ – Joe Feb 5 '13 at 0:22

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.