## Median in a stream of numbers

The** brute force** algorithm uses a vector and maintains a **sorted list**. In this case the complexity of adding an element is O(n). Therefore, for n elements, the worst case is O(n^2).

Instead we maintain 2 **priority queue**s i.e minHeap, maxHeap. We keep adding the numbers in both such that the number of elements in the maxheap is at max 1 greater than number of elements in the minHeap. Maintaining this constraint, allows us to get the median in O(1) time. Also, insertion becomes O(logn). Therefore, overall complexity is** O(nlogn)**.

#include <iostream> #include <queue> using namespace std; void insert(priority_queue<int> &maxHeap,priority_queue<int,vector<int>, greater<int> > &minHeap, int n) { if(maxHeap.size()==minHeap.size()) { if(!minHeap.empty() && n>minHeap.top()) { maxHeap.push(minHeap.top()); minHeap.pop(); minHeap.push(n); } else maxHeap.push(n); } else { if(n<maxHeap.top()) { minHeap.push(maxHeap.top()); maxHeap.pop(); maxHeap.push(n); } else minHeap.push(n); } } double getMedian(priority_queue<int> maxHeap,priority_queue<int,vector<int>, greater<int> > minHeap) { int a = minHeap.size(); int b = maxHeap.size(); if(a==0 && b==0) return -1; if((a+b)%2==0) return (double)(minHeap.top() + maxHeap.top())/2; else return maxHeap.top(); } int main() { priority_queue<int> maxHeap; priority_queue<int,vector<int>, greater<int> > minHeap; int a[] = {7,11,17,8,19,2,3,15,16}; int n = sizeof(a)/sizeof(a[0]); for(int i=0; i<n; i++) { insert(maxHeap,minHeap,a[i]); cout<<getMedian(maxHeap,minHeap)<<endl; } return 0; }

Advertisements

## 1 Comment »

### Leave a Reply

Advertisements

thanks for the content really useful.

Comment by anandharaj | May 3, 2012 |