Tuesday, September 24, 2013

How to find median in order of log n ?

Median in an infinite series of integers

Solution: Use 2 heaps: One MaxHeap and one MinHeap.

1) MaxHeap contains the smallest half of the received integers
2) MinHeap contains the largest half of the received integers

The integers in MaxHeap are always less than or equal to the integers in MinHeap. Also, the number of elements in MaxHeap is either equal to or 1 more than the number of elements in the MinHeap.

In the stream if we get 2n elements (at any point of time), MaxHeap and MinHeap will both contain equal number of elements (in this case, n elements in each heap).

Otherwise, if we have received 2n+1 elements, MaxHeap will contain n+1 and MinHeap n.

Let us find the Median: If we have 2n+1 elements (odd), the Median of received elements will be the largest element in the MaxHeap (nothing but the root of MaxHeap). Otherwise, the Median of received elements will be the average of largest element in the MaxHeap (nothing but the root of MaxHeap) and
minimum element in the MinHeap (nothing but the root of MinHeap). This can be calculated in O(1).

Inserting an element in heaps can be done O(logn). Note that, any heap containing n+1 elements might need one delete operation (and insertion to other heap) as well.

Total Time Complexity: O(logn).

Suppose we have sequence like : 1,9,2,0 then construction of heaps:

Insert 1: Insert to MaxHeap.

MaxHeap: {1}, MinHeap:{}

Insert 9: Insert to MinHeap. Since 9 is greater that 1 and MinHeap maintains the maximum elements.
MaxHeap: {1}, MinHeap:{9}


Insert 2: Insert MinHeap. Since 2 is less than all elements of MinHeap.
MaxHeap: {1,2}, MinHeap:{9}

Insert 0: Since MaxHeap already contains more than half; we have to delete the max element from MaxHeap and insert it to MinHeap. So, we have to remove 2 and insert into MinHeap. With that it becomes:
MaxHeap: {1}, MinHeap:{2,9}
Now, insert 0 to MaxHeap.


Via Narasimha Karumanchi Sir :

0 comments:

Post a Comment