electroRF
Member
Hi,
I'd appreciate your help with a question i'm trying to solve:
- you receive a stream of integers. Find the median value as new numbers are generated.
I read on algorithm which uses two Heaps:
MaxHeap - stores all the numbers below the median
MinHeap - Stores all the numbers above the median
I wrote below is the solution in details (in blue).
My question is:
They claim that insertion of new value takes O(log(n)), as the heaps are sorted.
However, how can one insert a value in the middle of a heap, without having to pop some of the items out, then push the new value, and then push the other values?
This would take more then O(log(n)).
Therefore, I don't understand how they reached O(log(n)).
Thank you very much for your help.
Use two priority heaps: a max heap for the values below the median,
and a min heap for the values above the median.
This will divide the elements roughly in half, with the middle two elements as the top of the two heaps.
This makes it trivial to find the median.
What do we mean by "roughly in half," though? "Roughly" means that, if we have an odd number of values, one heap will have an extra value.
Observe that the following is true:
• If maxHeap.size() > minHeap.size(),then heap1.topO will be the median.
• If maxHeap.size() == minHeap. sizeQ, then the average of maxHeap.topQ
and minHeap.top() will bethemedian.
By the way in which we rebalance the heaps, we will ensure that it is always maxHeap with extra element.
The algorithm works as follows. When a new value arrives, it is placed in the maxHeap if
the value is less than or equal to the median, otherwise it is placed into the minHeap.
The heap sizes can be equal, or the maxHeap may have one extra element.
This constraint can easily be restored by shifting an element from one heap to the other.
The median is available in constant time, by looking at the top element(s). Updates take 0(log(n)) time.
They shared C++ solution (although i'm interested in C).
I'd appreciate your help with a question i'm trying to solve:
- you receive a stream of integers. Find the median value as new numbers are generated.
I read on algorithm which uses two Heaps:
MaxHeap - stores all the numbers below the median
MinHeap - Stores all the numbers above the median
I wrote below is the solution in details (in blue).
My question is:
They claim that insertion of new value takes O(log(n)), as the heaps are sorted.
However, how can one insert a value in the middle of a heap, without having to pop some of the items out, then push the new value, and then push the other values?
This would take more then O(log(n)).
Therefore, I don't understand how they reached O(log(n)).
Thank you very much for your help.
Use two priority heaps: a max heap for the values below the median,
and a min heap for the values above the median.
This will divide the elements roughly in half, with the middle two elements as the top of the two heaps.
This makes it trivial to find the median.
What do we mean by "roughly in half," though? "Roughly" means that, if we have an odd number of values, one heap will have an extra value.
Observe that the following is true:
• If maxHeap.size() > minHeap.size(),then heap1.topO will be the median.
• If maxHeap.size() == minHeap. sizeQ, then the average of maxHeap.topQ
and minHeap.top() will bethemedian.
By the way in which we rebalance the heaps, we will ensure that it is always maxHeap with extra element.
The algorithm works as follows. When a new value arrives, it is placed in the maxHeap if
the value is less than or equal to the median, otherwise it is placed into the minHeap.
The heap sizes can be equal, or the maxHeap may have one extra element.
This constraint can easily be restored by shifting an element from one heap to the other.
The median is available in constant time, by looking at the top element(s). Updates take 0(log(n)) time.
They shared C++ solution (although i'm interested in C).
Code:
1 private Comparatorxlnteger> maxHeapComparator;
private Comparator<Integer>,minHeapComparator;
3 private PriorityQueue<Integer> maxHeap., minHeap;
4
5 public void addNewNumber(int randomNumber) {
/* Note: addNewNumber maintains a condition that
* maxHeap.sizeQ >= minHeap.sizeQ */
if (maxHeap.sizeQ == minHeap.sizeQ) {
if ((minHeap.peek() != null) &&
10 randomNumber > minHeap.peekQ) {
maxHeap.offer(minHeap.poll());
12 minHeap.offer(randomNumber);
13 } else {
14 maxHeap.offer(randomNumber);
15 }
16 } else {
if(randomNumber < maxHeap.peek()) {
18 minHeap.offer(maxHeap.poll());
19 maxHeap.offer(randomNumber);
20 }
21 else {
minHeap.offer(randomNumber);
23 }
24 }
25 }
26
27 public static double getMedian() {
28 /* maxHeap is always at least as big as minHeap. So if maxHeap
* is empty, then minHeap is also. */
30 if (maxHeap.isEmptyO) {
31 return 0;
32 }
33 if (maxHeap.sizeQ == minHeap.sizeQ) {
34 return ((double)minHeap.peek()+(double)maxHeap.peek()) / 2;
35 } else {
36 /* If maxHeap and minHeap are of different sizes., then
37 * maxHeap must have one extra element. Return maxHeap's
38 * top element.*/
39 return maxHeap.peek();
40 }
41 }
Last edited:
