Interview Classic 150 Questions P295 Median of Data Stream

---

Timeline

Timeline

2025-12-19

init

heap

---

Problem:

P295 Median of 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., the closest to the center).
• Max-heap, stores the smaller half (so the top element is the largest in the smaller half, i.e., the closest to the center).

When the total number of added numbers is odd, minHeap contains one more number than maxHeap, and the median is the top of minHeap. When the total number of added numbers is even, the two priority queues contain the same number of elements, and the median is the average of their tops. In particular, when the total number of added numbers 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
                        return ((double)max_heap.top() + (double)min_heap.top()) / 2;
                }
        }
};

leetcode hot 100 rewrite:

Two heaps:

#include <queue>
#include <vector>

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

class MedianFinder {
    private:
        priority_queue<int, vector<int>, std::less<int> > max_heap; // Stores the smaller part
        priority_queue<int, vector<int>, std::greater<int> > min_heap; // Stores 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
                        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
                        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
                        return max_heap.top();
                } else {
                        return (max_heap.top() + min_heap.top()) / 2.0;
                }
        }
};