Interview Classic 150 Questions P295 Find Median from Data Stream

---

Timeline

Timeline

2025-12-19

init

Heap

---

Problem:

P295 Find Median from Data Stream

https://leetcode.cn/problems/find-median-from-data-stream/description/

Use two priority queues, maxHeap and minHeap, to record numbers less than the median and numbers greater than or equal to the median respectively.

• Min-heap, stores the larger half (so the top element is the smallest in the larger half, i.e., closest to the center)
• Max-heap, stores the smaller half (so the top element is the largest in the smaller half, i.e., closest to the center)

When the total number of added numbers is odd, minHeap has one more number than maxHeap, and the median is the top of minHeap. When the total number is even, both priority queues have the same number of elements, and the median is the average of their tops. In particular, when the total number is 0, we add num to minHeap.

#include <vector>
#include <queue>
using std::priority_queue;
using std::vector;

class MedianFinder {
    private:
        priority_queue<int, vector<int>, std::less<int> > max_heap;
        priority_queue<int, vector<int>, std::greater<int> > min_heap;

    public:
        MedianFinder()
        {
        }

        void addNum(int num)
        {
                if (max_heap.empty()) {
                        max_heap.push(num);
                        return;
                }
                if ((max_heap.size() + min_heap.size()) & 0x1) { // Odd
                        int curr_median = max_heap.top();
                        if (num >= curr_median) {
                                min_heap.push(num);
                        } else {
                                max_heap.pop();
                                min_heap.push(curr_median);
                                max_heap.push(num);
                        }
                } else { // Even
                        if (num <= min_heap.top()) {
                                max_heap.push(num);
                        } else {
                                max_heap.push(min_heap.top());
                                min_heap.pop();
                                min_heap.push(num);
                        }
                }
        }

        double findMedian()
        {
                if ((max_heap.size() + min_heap.size()) & 0x1) { // Odd
                        return (double)max_heap.top();
                } else { // even number
                        return ((double)max_heap.top() + (double)min_heap.top()) / 2;
                }
        }
};

leetcode hot 100 rewrite:

Opposite heap:

#include <queue>
#include <vector>

using std::priority_queue;
using std::vector;

class MedianFinder {
    private:
        priority_queue<int, vector<int>, std::less<int> > max_heap; // store the smaller part
        priority_queue<int, vector<int>, std::greater<int> > min_heap; // store the larger part

    public:
        MedianFinder()
        {
        }

        void addNum(int num)
        {
                if (max_heap.empty()) {
                        max_heap.push(num);
                        return;
                }

                if ((max_heap.size() + min_heap.size()) % 2 != 0) { // odd number
                        int curr_mid = max_heap.top();
                        if (num >= curr_mid) {
                                min_heap.push(num);
                        } else {
                                min_heap.push(curr_mid);
                                max_heap.pop();
                                max_heap.push(num);
                        }

                } else { //even number
                        if (num <= min_heap.top()) {
                                max_heap.push(num);
                        } else {
                                max_heap.push(min_heap.top());
                                min_heap.pop();
                                min_heap.push(num);
                        }
                }
        }

        double findMedian()
        {
                if ((max_heap.size() + min_heap.size()) % 2 != 0) { // odd number
                        return max_heap.top();
                } else {
                        return (max_heap.top() + min_heap.top()) / 2.0;
                }
        }
};