Take the 2-minute tour ×

Wikipedia says:

Selection algorithms: Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time using heaps.

All it says is that it can be done, and not how.

Can you give me some start on how this can be done using heaps?

share|improve this question
I think it may be wrong about the median and k-th largest, but I would be very happy to be proved wrong about this, especially for the median. –  Paul R Apr 5 '10 at 18:01
Duplicate: stackoverflow.com/questions/810657/… –  Jacob Apr 5 '10 at 18:08
Not a duplicate. (I think, but could be wrong) this is not about selection algorithms, but about getting median to be O(1) time, after the heaps are created. –  Aryabhatta Apr 5 '10 at 18:10
@Paul R: if the heap is sorted, don't you just have to traverse the tree in post-order for k items to get the k-th largest? –  ANeves Apr 5 '10 at 18:14
@Jacob: this is not a duplicate of that question. In the other question, he had a very specific number of elements from which he's getting the median. In this question, there's no given number of elements, and the set can be of arbitrary size. The algorithm in the other question may be the same answer, but the question isn't the same. –  mmr Apr 5 '10 at 18:36
show 1 more comment

7 Answers

up vote 17 down vote accepted

You would use a min-max-median heap to find the min, max and median in constant time (and take linear time to build the heap). You can use order-statistics trees to find the kth smallest/largest value. Both of these data structures are described in this paper on min-max heaps [pdf link]. Min-max heaps are binary heaps that alternate between min-heaps and max-heaps.

From the paper: A min-max-median heap is a binary heap with the following properties:

1) The median of all elements is located at the root

2) The left subtree of the root is a min-max heap Hl of size ceiling[((n-1)/2)] containing elements less than or equal to the median. The right subtree is a max-min heap Hr of size floor[((n-1)/2)] containing only elements greater than or equal to the median.

The paper goes on to explain how to build such a heap.

Edit: Upon reading the paper more thoroughly it appears as though building the min-max-median heaps requires that you first find the median (FTA: "Find the median of all n elements using any one of the known linear-time algorithms"). That said, once you have built the heap you can maintain the median simply by maintaining the balance between the min-max heap on the left and the max-min heap on the right. DeleteMedian replaces the root with either the min of the max-min heap or the max of the min-max heap (whichever maintains the balance).

So if you plan on using a min-max-median heap to find the median of a fixed data set you're SOL but if you are using it on a changing data set it is possible.

share|improve this answer
Actually, both heaps can be either min-max or max-min and the algorithm would still work with the same overall complexity –  dhruvbird Apr 23 '11 at 14:37
add comment

See this wikipedia page on selection algorithms. In particular, look at the BFPRT algorithm and the Median of Medians algorithm. BFPRT is probabilistically linear, and is modelled on quicksort; Median of Medians is guaranteed linear, but has a large constant factor and so might take longer in practice, depending on the size of your dataset.

If you only have a few hundred or thousand elements from which to select the median, I suspect that a simple quicksort followed by direct indexing is easiest.

share|improve this answer
@Dale Hagglund: "using heaps"? –  Lazer Apr 5 '10 at 18:12
"linear" is incompatible with "using heaps" unless you're throwing in the pre-processing cost for free. However, I should have made that clear at the beginning of my post. –  Dale Hagglund Apr 5 '10 at 18:25
Is it really that hard to apply the heap concept to partitions and pivots? –  tloflin Apr 5 '10 at 18:39
@tlofin: sorry, but I'm not sure what you're asking. –  Dale Hagglund Apr 5 '10 at 19:28
Sorry, I was replying to eSKay. Guess I need to start using these "@"s. –  tloflin Apr 5 '10 at 20:52
add comment

There are likely better algorithms out there, but here's how I'd do it:

Have two buckets and a value. The value is the median, the two buckets are "bigger than median" and "smaller than median". For each element x in the array, rebalance the buckets such that big_bucket and small_bucket differ by no more than 1 in their size. When moving items from the big bucket to the small bucket they first must pass through the median value to get there (that is, a difference of 2 will successfully push an element from one bucket to the next - a difference of 1 will push an element from one bucket to the median value.) At the end of your first pass through the array the value should be your median.

share|improve this answer
@fbrereto: What would be the time complexity of your algorithm? I think this algorithm is NOT linear. –  Lazer Apr 5 '10 at 18:15
It'd be one pass through the original array, and the bucket operations would be push/pop, which can be done in constant time (as their size is known to be no more than N/2+1), so off the top of my head I suspect it can be done in O(N). Please correct me if I've missed something. –  fbrereto Apr 5 '10 at 20:08
Hrm... one would have to keep the buckets sorted, which is not an O(N) operation (mod a radix sort). –  fbrereto Apr 5 '10 at 20:11
@fbrereto: store minbucket and maxbucket each as heaps. It's basically the same concept as the other solutions. Not sure if the explicit middle element makes much difference. –  smci Aug 26 '12 at 9:36
add comment

perhaps it wasnt around when the original question was asked, but now wiki has a link to the source, and here it is: http://ftp.cs.purdue.edu/research/technical_reports/1991/TR%2091-027.pdf

specifically, go to page 17, and look at the description of RSEL4. They prove in theorem 3.2 that the time complexity of this k-th selection algorithm is O(k). so it would take you O(n) to build the heap, and an extra O(k) to find k-th smallest item.

its not really as straight forward as some of the other answers have suggested

share|improve this answer
add comment

My runnable Java implementation of the selection algorithm, which selects the Kth smallest element of an given array in guaranteed linear time.


share|improve this answer
It changes order of given array. Input: { 2, 3, 5, 1, 9, 10, -22}. Output: { 2, 3, 5, 1, 9, 10, -22} –  rafalmag Nov 9 '12 at 21:44
Yeah, the classic guaranteed linear select will rummage through the array switching things around a pivot. That's expected behavior. –  Trevor Alexander Nov 27 '13 at 8:16
Quick selection is another algorithm that is more approachable than median of median, at least to me. However, it also switches elements just like quick sort (which is in-place sorting) –  Zhile Zou Mar 7 at 1:34
add comment

Obviously, min and max in O(n) is easy and don't require a heap.

K'th largest can be done fairly simply by maintaining a k-sized heap of the top k values so far. Runtime would be O(n*logk). You could call that linear time if k is fixed size and k << n.

I don't think median is possible though. Just creating an O(n) sized heap requires O(n*logn) time.

Edit: Ok, after thinking about this a bit more, IVlad is right. You can create a heap in O(n), for a fixed size. But... that doesn't help the OP with his Median question. The linear heap creation technique only produces a valid heap as its final output. The simple approach of doing n inserts, resulting in a valid heap after each step is O(n*logn).

It seems to me that using heaps to find the median would require the use of those running sub-heaps. For instance, there was an answer posted here (that seems to be deleted now) that linked to a blog post suggesting an algorithm for this problem. It tracked the running median using two heaps (the smaller half and the larger half) as it does a single pass through the data. That would require the slower, naive heap approach becuase it depends on maintaining valid heaps as it inserts and removes from them.

Is there some other way to find the median using the linear one-shot heap creation technique?

share|improve this answer
"Just creating an O(n) sized heap requires O(n *logn) time" - wrong, you can create a heap in O(N) time. –  IVlad Apr 5 '10 at 18:14
@IVlad - You can create a heap for already-sorted data in O(n) time, and you can create a fixed-size heap in O(n) time, but I don't see either of those preconditions in the quesion. –  Jeffrey L Whitledge Apr 5 '10 at 18:35
If the data is already sorted, then you don't need a heap to find the median, or any of the other objectives in the OP. –  Alan Apr 5 '10 at 18:41
@Jeffrey L Whitledge - you can create a heap for unsorted data in O(n) time as well. A sorted set of data is already a heap, so creating a heap out of that is O(1) actually. I'm pretty sure the question refers to a fixed-sized input, "selection algorithm" implies that. –  IVlad Apr 5 '10 at 18:53
If the question refers to a "fixed-size input", then the expression "linear time" is meaningless. By "fixed-size heap" I meant one that may be used to find, say, the 10th largest element of an unsorted set. An algorithm to find the m-th largest or smallest value would be O(n), where n is the input size and m is a fixed number intrensic to the algorithm. If m is allowed to vary as part of the input, then heap-manipulation is no longer constant time, but becomes O(n log m). –  Jeffrey L Whitledge Apr 5 '10 at 19:04
add comment

if you know more about heap data structure, you will easily understand that that s actually the case. heap structure can be built in O(n) time, there is min heap and max heap. min heap root element will give you the smallest element. max heap root element will give you the max element. Just by building the heap you find the min and max. same idea for median and kth largest, while building your heap, you can find the median and kth largest by looking at left or right branch of the tree and by keeping a constant amount of memory to store the element number. etc.

share|improve this answer
@user177883: how will you build a heap so that the root is the median? –  Lazer Apr 9 '10 at 6:40
add comment

Your Answer


