Ronzii's Blog

Just your average geek's blog

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 queues 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;
}

March 30, 2012 Posted by | C++ | , , , | 1 Comment

Random Number Generation

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
int rand5()
{
    return rand()%5;
}
int rand7()
{
    int vals[5][5] =
    {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };

    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}
int main()
{
    srand(time(NULL));
    cout<<rand7();
    return 0;
}

March 29, 2012 Posted by | C++ | , , , | Leave a comment