52

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?

6
  • 4
    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, 2010 at 18:01
  • 2
    Duplicate: stackoverflow.com/questions/810657/…
    – Jacob
    Apr 5, 2010 at 18:08
  • 3
    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, 2010 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, 2010 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, 2010 at 18:36

7 Answers 7

22

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]. 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 tree 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.

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.

5
  • 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, 2011 at 14:37
  • Actually, sufficient and simpler is just a min(max) heap for the tree with elements no less(greater) than the median.
    – greybeard
    Apr 29, 2021 at 6:07
  • How do I [exploit heaps to find the median in linear time]? Essentially, this answer and the paper it is based upon don't give a clue. (I think heap the wrong tree to bark up.)
    – greybeard
    Apr 29, 2021 at 6:18
  • (What is FTA spelled out, here?)
    – greybeard
    Apr 29, 2021 at 6:19
  • @greybeard, just guessing, but From The Article maybe?
    – trincot
    Sep 7, 2022 at 21:55
4

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.

5
  • 2
    @Dale Hagglund: "using heaps"?
    – Lazer
    Apr 5, 2010 at 18:12
  • 2
    "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. Apr 5, 2010 at 18:25
  • Is it really that hard to apply the heap concept to partitions and pivots?
    – tloflin
    Apr 5, 2010 at 18:39
  • @tlofin: sorry, but I'm not sure what you're asking. Apr 5, 2010 at 19:28
  • Sorry, I was replying to eSKay. Guess I need to start using these "@"s.
    – tloflin
    Apr 5, 2010 at 20:52
4

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.

4
  • @fbrereto: What would be the time complexity of your algorithm? I think this algorithm is NOT linear.
    – Lazer
    Apr 5, 2010 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, 2010 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, 2010 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, 2012 at 9:36
3

Perhaps it wasn't around when the original question was asked, but now wiki has a link to the source, and here it has been: 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.

It's not really as straightforward as some of the other answers have suggested.

1
1

Store the first integer in the array and set a counter to 1. Then loop through the remaining integers in the vector. If the current integer in the array is the same as the one stored, the counter is increased by one, otherwise the counter is decreased by one. If the counter ever reaches zero, throw away the stored integer and replace it with the current integer in the array. When you finally have looped through all integers you are left with one candidate. You then need to loop through the array again and count the occurrence of the candidate to verify that this really is a dominator.

static int FindDominator(int[] arr)
{
int counter = 1;
int candidate = arr[0];
for(int i = 1; i < n; i++)
{
   if(arr[i] == candidate) counter++
    else 
   {
        counter--;
        if(counter == 0) { candidate = arr[i]; counter = 1; }
    }
}
counter = 0;
for(int i = 0;  i < n; i++)
{
    if(arr[i] == candidate) counter++;
}
if(counter > n / 2) return candidate;
else return -1;
}
0

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.

1
  • @user177883: how will you build a heap so that the root is the median?
    – Lazer
    Apr 9, 2010 at 6:40
-1

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?

5
  • "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, 2010 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. Apr 5, 2010 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, 2010 at 18:41
  • 1
    @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, 2010 at 18:53
  • 1
    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). Apr 5, 2010 at 19:04

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.