<p>Assume for simplicity that $n = 2^m$. Use the linear time selection algorithm to find the elements at positions $2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given $k$, find $t$ such that $2^{t-1} \leq k \leq 2^t$; note that $2^t \leq 2k$. Filter out all elements of rank at most $2^t$, and now use the linear time selection algorithm to find the element at position $k$ in time $O(2^t) = O(k)$.</p>

<p><strong>Clarification:</strong> It might seem that the preprocessing takes time $\Theta(n\log n)$, and that is indeed the case if you're not careful. Here is how to do the preprocessing in linear time:</p>

<pre><code>while n &gt; 0:
  find the (lower) median m of A[0..n-1]
  partition A in-place so that A[n/2-1] = m
  n = n/2
</code></pre>

<p>The in-place partitioning is done like in quicksort. The running time is linear in $n + n/2 + n/4 + \cdots + 1 &lt; 2n$, and so linear. In the end, the array $A$ satisfies the following property: for each $k$, $A[0..n/2^k-1]$ consists of the $n/2^k$ smallest elements.</p>

CC BY-SA 3.0
2013-06-23T15:01:54.603Z
will this algorithm work on not sorted array as well?
Idan
CC BY-SA 3.0
2013-06-23T16:03:26.833Z
Naturally. If the array is sorted that you can solve this in $O(1)$ without preprocessing. Perhaps you are not aware of the linear time selection algorithm that can find the $k$th largest element in time $O(n)$?
Yuval Filmus
CC BY-SA 3.0
2013-06-23T17:10:41.823Z
Yuval is referring to http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm and you might also want to look at http://en.wikipedia.org/wiki/Partial_sorting#Direct_application_of_the_linear-time_selection_algorithm for a more straightforward way to use this.
András Salamon
CC BY-SA 3.0
2013-06-23T17:12:51.600Z
@Yuval Filmus: Are you not running the algorithm $\log n$ times, for a total of $n \log n$ steps?  Or did you have some kind of interleaving in mind?
András Salamon
CC BY-SA 3.0
2013-06-23T20:20:09.593Z
@AndrásSalamon: If you read the answer given by Jeremy (which looks to me almost the same as this one) you see that you first process the whole array, then the first half, and so on.
Radu GRIGore
CC BY-SA 3.0
2013-06-23T20:31:21.610Z
@AndrásSalamon Radu is correct. After you find the median, you partition the array (in-place) into its lower and upper half, then recurse on the lower half. The running time is then proportional to $n+n/2+n/4+\cdots+1 < 2n$.
Yuval Filmus
CC BY-SA 3.0
2013-06-23T23:12:55.437Z
Incidentally this algorithm appears as a subroutine in my answer to an earlier question: http://cstheory.stackexchange.com/questions/17378/finding-max-of-two-elements-in-linear-time-with-restriction/17384#17384
David Eppstein
CC BY-SA 3.0
2013-06-24T10:54:35.257Z
@DavidEppstein: Ha! I was _sure_ I saw this somewhere before. Thanks for the link.
Radu GRIGore
CC BY-SA 3.0
2013-06-23T14:59:01.970Z
2013-06-23T20:36:30.320Z
2013-06-23T20:36:30.320Z
Yuval Filmus
<p>First use <span class="math-container">$O(n)$</span> to build a min-heap. It is known that we can use <span class="math-container">$O(k)$</span> to find the <span class="math-container">$k$</span> smallest elements in a min-heap: </p>

<p><em>Frederickson, Greg N.</em>, <a href="http://dx.doi.org/10.1006/inco.1993.1030" rel="nofollow noreferrer"><strong>An optimal algorithm for selection in a min-heap</strong></a>, Inf. Comput. 104, No. 2, 197-214 (1993). <a href="https://zbmath.org/?q=an:0818.68065" rel="nofollow noreferrer">ZBL0818.68065</a>..</p>

CC BY-SA 4.0
2019-05-17T13:59:45.397Z
I don't see how we can extract the smallest $k$ elements from a min-heap in time $O(k)$, as removing each element takes logarithmic time in the size of the heap. Could you clarify what you had in mind here? Thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-19T13:36:26.030Z
@a3nm It is indeed not a simple algorithm, but I've updated the reference.
hqztrue
CC BY-SA 4.0
2019-05-27T13:53:09.033Z
Sorry, as far as I can tell the reference that you added just talks about selecting the $k$-th smallest element (i.e., a single element, not the $k$ smallest elements) in time $O(k)$. I don't see how this would adapt to extracting the $k$ smallest elements. Could you maybe explain or update the reference?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-27T14:45:52.450Z
@a3nm yes the reference only gives you the $k$-th smallest element $x$. However after knowing that, you can just perform a dfs in the heap to find all elements $<x$ in $O(k)$.
hqztrue
CC BY-SA 4.0
2019-05-28T16:24:25.460Z
Sorry I don't see which DFS you would perform to find these elements? (Some of them may not be ancestors of the $k$-th smallest element in the heap, i.e., as far as I can tell locating, e.g., the $k/2$-th element knowing the position of the $k$-th element is not trivial.)
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-29T05:55:36.103Z
@a3nm dfs(node p){print(p->val); if (p->l->val<x)dfs(p->l); if (p->r->val<x)dfs(p->r);} and you perform dfs(root).
hqztrue
CC BY-SA 4.0
2019-05-29T09:08:10.063Z
Ahhh right, so you're saying that once we know the $k$-th smallest value in the heap (no matter where it is located in the heap) then it becomes easy to traverse the heap from the root and print all values that are smaller. Yeah, that makes sense, thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2019-05-16T09:02:57.490Z
2019-05-19T13:35:09.520Z
2019-05-19T13:35:09.520Z
hqztrue
<p>Use linear time selection to find the $k$th largest element, then do a partition step from quicksort using the $k$th largest element as the pivot.</p>

CC BY-SA 3.0
2013-06-23T19:35:28.070Z
The original question mentions that $k$ is not known at preprocessing time....
J.y B.y
CC BY-SA 3.0
2013-06-23T22:17:55.743Z
I see. My mistake.
jbapple
CC BY-SA 3.0
2013-06-23T18:33:40.033Z
2013-06-23T18:33:40.033Z
jbapple
<h2>Preprocess the array of $n$ values in time $O(n)$:</h2>

<ul>
<li>$i\leftarrow n$</li>
<li>while $i&gt;2$
<ul>
<li>Compute the median $m$ of $A[1..i]$ in time $O(i)$</li>
<li>partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.</li>
<li>$i \leftarrow \lfloor i/2 \rfloor$</li>
</ul></li>
</ul>

<p>The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$</p>

<h2>Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:</h2>

<ul>
<li>$l\leftarrow \lfloor \log_2 k \rfloor$</li>
<li>select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$</li>
<li>partition $A[2^l..2^{l+1}]$ by $x$ in the same time</li>
</ul>

<p>$A[1..k]$ contains the $k$ smallest elements.</p>

<h2>References:</h2>

<ul>
<li>In 1999, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.9432">Dor and Zwick</a> gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.</li>
</ul>

CC BY-SA 3.0
2013-06-23T20:14:47.570Z
I guess the outer loop is supposed to be 'for i in $\{2^{\lceil\lg n\rceil},\dots,4,2,1\}$'. Is your algorithm different from the one in Yuval Filmus' answer?
Radu GRIGore
CC BY-SA 3.0
2013-06-23T20:39:16.520Z
This is a generalization of my algorithm to arbitrary $n$. It also spells out some implementation details which were (deliberately) left out from my answer.
Yuval Filmus
CC BY-SA 3.0
2013-06-24T12:28:01.190Z
@YuvalFilmus Do you wish to imply by your comment that my answer is unethically close to yours? This is the solution which came to mind when I reviewed the question. I saw that you posted a similar one, but found it unclear, so I wrote my own (as opposed to doing a major edit of yours). What matters ultimately is the quality of the answers on the systems, not really who wrote them: the badges and reputation are only incentives, not objectives in themselves.
J.y B.y
CC BY-SA 3.0
2013-06-24T14:40:21.060Z
@Jeremy Not at all; Just that the two solutions are the same (but yours works for arbitrary $n$), and that I didn't flesh out the details in case it was actually a homework question.
Yuval Filmus
CC BY-SA 3.0
2013-06-25T13:31:53.643Z
Oh :( Sorry about that then. (Althought I would still think giving complete answers to be a priority over assignment suspicions)
J.y B.y
CC BY-SA 3.0
2013-06-23T19:53:29.210Z
2013-06-24T12:22:00.557Z
2013-06-24T12:22:00.557Z
J.y B.y
<p>This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 &lt;= k &lt;= n</p>

<p>I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!</p>

<p>quick notes:
-the order of the k smallest elements is not important
-the elements in the array are number , might be integers and might be not (so no radix sort)
-the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .</p>

CC BY-SA 3.0
2013-06-23T14:44:35.480Z
How about using a min-heap?
Shir
CC BY-SA 3.0
2013-06-23T14:44:45.073Z
Look at k-skyband and top-k computation.  The paper http://www.cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf has a nice review of related literature.
András Salamon
CC BY-SA 3.0
2013-06-23T14:47:01.547Z
Shir-I have examined the min-heap idea . however , in order to print the k smallest numbers in min heap is in O(klogn) time and not O(k) as required
Idan
CC BY-SA 3.0
2013-06-23T14:56:24.033Z
@idannik of course, silly me.
Shir
CC BY-SA 3.0
2013-06-23T20:07:07.880Z
@idannik: Why do you think it takes $\Omega(k \log n)$ time to find the $k$ smallest elements in a min-heap?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2013-06-23T21:20:16.397Z
I don't think this is research-level. It looks like an assignment. Where did you find it?
Kaveh
CC BY-SA 3.0
2013-06-24T16:01:59.960Z
I don't get it.  I thought it was known that you could find the *k* smallest elements in *O*(*k*) time without preprocessing too.
Zsbán Ambrus
CC BY-SA 3.0
2013-06-24T17:10:31.307Z
@ZsbánAmbrus That's patently false. Even finding the minimum takes $\Omega(n)$ time.
Yuval Filmus
CC BY-SA 3.0
2013-06-25T08:10:30.393Z
Ah, $ O(k) $, not $ O(n) $. Sorry.
Zsbán Ambrus
<sorting>
finding smallest k elements in array in O(k)
Idan
# finding smallest k elements in array in O(k)

(Asked by: username_0 on 2013-06-23)

This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 <= k <= n

I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!

quick notes:
-the order of the k smallest elements is not important
-the elements in the array are number , might be integers and might be not (so no radix sort)
-the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .

**Tags:** sorting

> **Comments:**
> **username_1**: How about using a min-heap?  
> **username_2**: Look at k-skyband and top-k computation.  The paper http://www.cs.sfu.ca/~jpei/publications/subsky_tkde07.pdf has a nice review of related literature.  
> **username_0**: username_1-I have examined the min-heap idea . however , in order to print the k smallest numbers in min heap is in O(klogn) time and not O(k) as required  
> **username_1**: @idannik of course, silly me.  
> **username_3**: @idannik: Why do you think it takes $\Omega(k \log n)$ time to find the $k$ smallest elements in a min-heap?  
> **username_4**: I don't think this is research-level. It looks like an assignment. Where did you find it?  
> **username_5**: I don't get it.  I thought it was known that you could find the *k* smallest elements in *O*(*k*) time without preprocessing too.  
> **username_6**: @ZsbánAmbrus That's patently false. Even finding the minimum takes $\Omega(n)$ time.  
> **username_5**: Ah, $ O(k) $, not $ O(n) $. Sorry.  

---

## 4 answers

### Answer by username_12 on 2013-06-23. Score: 26 | Accepted answer

## Preprocess the array of $n$ values in time $O(n)$:

* $i\leftarrow n$
* while $i>2$
  + Compute the median $m$ of $A[1..i]$ in time $O(i)$
  + partition $A[1..i]$ into $A[1..i/2-1] \leq m$ and $A[i/2+1..i]\geq m$ in the same time.
  + $i \leftarrow \lfloor i/2 \rfloor$

The total precomputation time is within $O(1+2+4+...+n)\subseteq O(n)$

## Answer a query for the $k$ smallest elements in $A$ in time $O(k)$:

* $l\leftarrow \lfloor \log\_2 k \rfloor$
* select the $(k-2^l)$th element $x$ of $A[2^l..2^{l+1}]$ in time $O(2^l)\subseteq O(k)$
* partition $A[2^l..2^{l+1}]$ by $x$ in the same time

$A[1..k]$ contains the $k$ smallest elements.

## References:

* In 1999, [Dor and Zwick](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.9432) gave an algorithm to compute the median of $n$ elements in time within $2.942 n + o(n)$ comparisons, which yields an algorithm to select the $k$th element from $n$ unordered elements in less than $6n$ comparisons.

> **Comments:**
> **username_7**: I guess the outer loop is supposed to be 'for i in $\{2^{\lceil\lg n\rceil},\dots,4,2,1\}$'. Is your algorithm different from the one in username_6' answer?  
> **username_6**: This is a generalization of my algorithm to arbitrary $n$. It also spells out some implementation details which were (deliberately) left out from my answer.  
> **username_12**: @YuvalFilmus Do you wish to imply by your comment that my answer is unethically close to yours? This is the solution which came to mind when I reviewed the question. I saw that you posted a similar one, but found it unclear, so I wrote my own (as opposed to doing a major edit of yours). What matters ultimately is the quality of the answers on the systems, not really who wrote them: the badges and reputation are only incentives, not objectives in themselves.  
> **username_6**: @Jeremy Not at all; Just that the two solutions are the same (but yours works for arbitrary $n$), and that I didn't flesh out the details in case it was actually a homework question.  
> **username_12**: Oh :( Sorry about that then. (Althought I would still think giving complete answers to be a priority over assignment suspicions)  

---

### Answer by username_6 on 2013-06-23. Score: 15

Assume for simplicity that $n = 2^m$. Use the linear time selection algorithm to find the elements at positions $2^{m-1},2^{m-2},2^{m-3},\ldots,1$; this takes linear time. Given $k$, find $t$ such that $2^{t-1} \leq k \leq 2^t$; note that $2^t \leq 2k$. Filter out all elements of rank at most $2^t$, and now use the linear time selection algorithm to find the element at position $k$ in time $O(2^t) = O(k)$.
Clarification: It might seem that the preprocessing takes time $\Theta(n\log n)$, and that is indeed the case if you're not careful. Here is how to do the preprocessing in linear time:
while n > 0:
  find the (lower) median m of A[0..n-1]
  partition A in-place so that A[n/2-1] = m
  n = n/2

The in-place partitioning is done like in quicksort. The running time is linear in $n + n/2 + n/4 + \cdots + 1 < 2n$, and so linear. In the end, the array $A$ satisfies the following property: for each $k$, $A[0..n/2^k-1]$ consists of the $n/2^k$ smallest elements.

> **Comments:**
> **username_0**: will this algorithm work on not sorted array as well?  
> **username_6**: Naturally. If the array is sorted that you can solve this in $O(1)$ without preprocessing. Perhaps you are not aware of the linear time selection algorithm that can find the $k$th largest element in time $O(n)$?  
> **username_2**: Yuval is referring to http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm and you might also want to look at http://en.wikipedia.org/wiki/Partial_sorting#Direct_application_of_the_linear-time_selection_algorithm for a more straightforward way to use this.  
> **username_2**: @username_6: Are you not running the algorithm $\log n$ times, for a total of $n \log n$ steps?  Or did you have some kind of interleaving in mind?  
> **username_7**: @AndrásSalamon: If you read the answer given by Jeremy (which looks to me almost the same as this one) you see that you first process the whole array, then the first half, and so on.  
> **username_6**: @AndrásSalamon Radu is correct. After you find the median, you partition the array (in-place) into its lower and upper half, then recurse on the lower half. The running time is then proportional to $n+n/2+n/4+\cdots+1 < 2n$.  
> **username_8**: Incidentally this algorithm appears as a subroutine in my answer to an earlier question: http://cstheory.stackexchange.com/questions/17378/finding-max-of-two-elements-in-linear-time-with-restriction/17384#17384  
> **username_7**: @DavidEppstein: Ha! I was _sure_ I saw this somewhere before. Thanks for the link.  

---

### Answer by username_9 on 2019-05-16. Score: 3

First use $O(n)$ to build a min-heap. It is known that we can use $O(k)$ to find the $k$ smallest elements in a min-heap:

*Frederickson, Greg N.*, [**An optimal algorithm for selection in a min-heap**](http://dx.doi.org/10.1006/inco.1993.1030), Inf. Comput. 104, No. 2, 197-214 (1993). [ZBL0818.68065](https://zbmath.org/?q=an:0818.68065)..

> **Comments:**
> **username_10**: I don't see how we can extract the smallest $k$ elements from a min-heap in time $O(k)$, as removing each element takes logarithmic time in the size of the heap. Could you clarify what you had in mind here? Thanks!  
> **username_9**: @a3nm It is indeed not a simple algorithm, but I've updated the reference.  
> **username_10**: Sorry, as far as I can tell the reference that you added just talks about selecting the $k$-th smallest element (i.e., a single element, not the $k$ smallest elements) in time $O(k)$. I don't see how this would adapt to extracting the $k$ smallest elements. Could you maybe explain or update the reference?  
> **username_9**: @a3nm yes the reference only gives you the $k$-th smallest element $x$. However after knowing that, you can just perform a dfs in the heap to find all elements $<x$ in $O(k)$.  
> **username_10**: Sorry I don't see which DFS you would perform to find these elements? (Some of them may not be ancestors of the $k$-th smallest element in the heap, i.e., as far as I can tell locating, e.g., the $k/2$-th element knowing the position of the $k$-th element is not trivial.)  
> **username_9**: @a3nm dfs(node p){print(p->val); if (p->l->val<x)dfs(p->l); if (p->r->val<x)dfs(p->r);} and you perform dfs(root).  
> **username_10**: Ahhh right, so you're saying that once we know the $k$-th smallest value in the heap (no matter where it is located in the heap) then it becomes easy to traverse the heap from the root and print all values that are smaller. Yeah, that makes sense, thanks!  

---

### Answer by username_11 on 2013-06-23. Score: 0

Use linear time selection to find the $k$th largest element, then do a partition step from quicksort using the $k$th largest element as the pivot.

> **Comments:**
> **username_12**: The original question mentions that $k$ is not known at preprocessing time....  
> **username_11**: I see. My mistake.  

---

