Two Heap

Question 1

295. Find Median from Data Stream
     Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.
     For example,
     [2,3,4], the median is 3
     [2,3], the median is (2 + 3) / 2 = 2.5
     Design a data structure that supports the following two operations:
     • void addNum(int num) - Add a integer number from the data stream to the data structure.
     • double findMedian() - Return the median of all elements so far.

TC – O(logN)
SC-O(1)

Answer 1

Takeaway:
1. Need to discuss TC & SC.
2. Pay attention on how to balance the two heaps in add method by ensuring that maxheap have 1+minHeap.size() elements.
if(maxHeap.isEmpty()|| maxHeap.peek()>=num){
maxHeap.offer(num);
}else{
minHeap.offer(num);
}
if(maxHeap.size()>(minHeap.size()+1)){
minHeap.offer(maxHeap.poll());
}else if(maxHeap.size()
3. Calculation of median:-
//return (minHeap.peek()+maxHeap.peek())/2;(WRONG)
return maxHeap.peek() / 2.0 + minHeap.peek() / 2.0;
Pseudo Code:
1. We can store the first half of numbers (i.e., smallNumList) in a Max Heap. We should use a Max Heap as we are interested in knowing the largest number in the first half. Descending order.
2. We can store the second half of numbers (i.e., largeNumList) in a Min Heap, as we are interested in knowing the smallest number in the second half. Ascending order.
3. We can insert a number in the Max Heap (i.e. first half) if the number is smaller than the top (largest) number of the heap.
4. After every insertion, we will balance the number of elements in both heaps, so that they have an equal number of elements.
5. If the count of numbers is odd, let’s decide to have more numbers in max-heap than the Min Heap.
6. Return average of top value from both the heap in case number of elements in both the heaps are equal otherwise return top element from Max Heap.