หาค่ามัธยฐานจากสตรีมข้อมูลใน C++ (Find Median from Data Stream)

ภาพรวมปัญหา

ออกแบบคลาสที่รองรับ:
- addNum(num): เพิ่มตัวเลข
- findMedian(): คืนค่ามัธยฐานของตัวเลขทั้งหมดที่เพิ่มมา

วิธีแก้ปัญหา: Two Heaps

• Max Heap (left): เก็บครึ่งล่าง (ค่าน้อยกว่ามัธยฐาน) — ดึง max ได้ O(1)
• Min Heap (right): เก็บครึ่งบน (ค่ามากกว่ามัธยฐาน) — ดึง min ได้ O(1)
• รักษา invariant: |left.size() - right.size()| ≤ 1 และ left.top() ≤ right.top()

addNum(num)

1. ถ้า left ว่างหรือ num < left.top() → push left
2. มิฉะนั้น → push right
3. Rebalance: ถ้า left < right → ย้าย top right ไป left
4. ถ้า left > right + 1 → ย้าย top left ไป right

findMedian()

• left > right → left.top()
• left == right → (left.top() + right.top()) / 2

โค้ด C++

#include <bits/stdc++.h>
using namespace std;

class MedianFinder {
    priority_queue<int> left; // max heap
    priority_queue<int, vector<int>, greater<int>> right; // min heap
public:
    void addNum(int num) {
        if (left.empty() || num < left.top()) left.push(num);
        else right.push(num);
        if (left.size() < right.size()) {
            left.push(right.top()); right.pop();
        }
        if (left.size() - right.size() > 1) {
            right.push(left.top()); left.pop();
        }
    }
    double findMedian() {
        return left.size() > right.size() ? left.top() : (left.top() + right.top()) * 0.5;
    }
};

int main() {
    MedianFinder ob;
    ob.addNum(10); ob.addNum(15); cout << ob.findMedian() << endl; // 12.5
    ob.addNum(25); ob.addNum(30); cout << ob.findMedian() << endl; // 20
    ob.addNum(40); cout << ob.findMedian(); // 25
}

การวิเคราะห์ความซับซ้อน

• addNum: O(log n)
• findMedian: O(1)
• พื้นที่: O(n)