Find Median from Data Stream - rFronteddu/general_wiki GitHub Wiki

  • The median is the middle value in an ordered integer list.
  • If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.
  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.
import java.util.PriorityQueue;
import java.util.Collections;

class MedianFinder {
    // To store the smaller half of the numbers
    private PriorityQueue<Integer> maxHeap;

    // To store the larger half of the numbers
    private PriorityQueue<Integer> minHeap; 

    public MedianFinder() {
        // Java provides a min-heap by default, 
        // so we use Collections.reverseOrder() to simulate a max-heap.
        maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        minHeap = new PriorityQueue<>();
    }
    
    public void addNum(int num) {
        // Add to max heap
        maxHeap.offer(num);

        // Ensure every number in maxHeap is less than every number in minHeap
        minHeap.offer(maxHeap.poll());
        
        // If the heaps are unbalanced (maxHeap has more elements than minHeap)
        if (maxHeap.size() < minHeap.size()) {
            maxHeap.offer(minHeap.poll());
        }
    }
    
    public double findMedian() {
        // If maxHeap has more elements, the median is the root of maxHeap
        // remember that here maxHeap stores the smaller half of the numbers
        // since we have odd numbers, the top of the max heap is the median.
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.peek();
        }

        // If both heaps are balanced, the median is the average of the two roots
        else {
            return (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}
⚠️ **GitHub.com Fallback** ⚠️