Programming Interview Questions 13: Median of Integer Stream | Arden DertatArden Dertat

Programming Interview Questions 13: Median of Integer Stream | Arden DertatArden Dertat
https://gist.github.com/Vedrana/3675434

	public class MedianOfIntegerStream {
	public Queue<Integer> minHeap;
	public Queue<Integer> maxHeap;
	public int numOfElements;
	public MedianOfIntegerStream() {
	minHeap = new PriorityQueue<Integer>();
	maxHeap = new PriorityQueue<Integer>(10, new MaxHeapComparator());
	numOfElements = 0;
	}
	public void addNumberToStream(Integer num) {
	maxHeap.add(num);
	if (numOfElements%2 == 0) {
	if (minHeap.isEmpty()) {
	numOfElements++;
	return;
	}
	else if (maxHeap.peek() > minHeap.peek()) {
	Integer maxHeapRoot = maxHeap.poll();
	Integer minHeapRoot = minHeap.poll();
	maxHeap.add(minHeapRoot);
	minHeap.add(maxHeapRoot);
	}
	} else {
	minHeap.add(maxHeap.poll());
	}
	numOfElements++;
	}
	public Double getMedian() {
	if (numOfElements%2 != 0)
	return new Double(maxHeap.peek());
	else
	return (maxHeap.peek() + minHeap.peek()) / 2.0;
	}
	private class MaxHeapComparator implements Comparator<Integer> {
	@Override
	public int compare(Integer o1, Integer o2) {
	return o2 - o1;
	}
	}

class streamMedian: def __init__(self): self.minHeap, self.maxHeap = [], [] self.N=0   def insert(self, num): if self.N%2==0: heapq.heappush(self.maxHeap, -1*num) self.N+=1 if len(self.minHeap)==0: return if -1*self.maxHeap[0]>self.minHeap[0]: toMin=-1*heapq.heappop(self.maxHeap) toMax=heapq.heappop(self.minHeap) heapq.heappush(self.maxHeap, -1*toMax) heapq.heappush(self.minHeap, toMin) else: toMin=-1*heapq.heappushpop(self.maxHeap, -1*num) heapq.heappush(self.minHeap, toMin) self.N+=1   def getMedian(self): if self.N%2==0: return (-1*self.maxHeap[0]+self.minHeap[0])/2.0 else: return -1*self.maxHeap[0]

http://www.geeksforgeeks.org/median-of-stream-of-integers-running-integers/

int getMedian(int e, int &m, Heap &l, Heap &r)

{

    // Are heaps balanced? If yes, sig will be 0

    int sig = Signum(l.GetCount(), r.GetCount());

    switch(sig)

    {

    case 1: // There are more elements in left (max) heap

        if( e < m ) // current element fits in left (max) heap

        {

            // Remore top element from left heap and

            // insert into right heap

            r.Insert(l.ExtractTop());

            // current element fits in left (max) heap

            l.Insert(e);

        }

        else

        {

            // current element fits in right (min) heap

            r.Insert(e);

        }

        // Both heaps are balanced

        m = Average(l.GetTop(), r.GetTop());

        break;

    case 0: // The left and right heaps contain same number of elements

        if( e < m ) // current element fits in left (max) heap

        {

            l.Insert(e);

            m = l.GetTop();

        }

        else

        {

            // current element fits in right (min) heap

            r.Insert(e);

            m = r.GetTop();

        }

        break;

    case -1: // There are more elements in right (min) heap

        if( e < m ) // current element fits in left (max) heap

        {

            l.Insert(e);

        }

        else

        {

            // Remove top element from right heap and

            // insert into left heap

            l.Insert(r.ExtractTop());

            // current element fits in right (min) heap

            r.Insert(e);

        }

        // Both heaps are balanced

        m = Average(l.GetTop(), r.GetTop());

        break;

    }

    // No need to return, m already updated

    return m;

}

Read full article from Programming Interview Questions 13: Median of Integer Stream | Arden DertatArden Dertat