Tìm trung vị từ luồng dữ liệu (Find Median from Data Stream) trong C++

Thiết kế cấu trúc dữ liệu hỗ trợ:

• addNum(num): thêm số vào luồng.
• findMedian(): trả về trung vị của tất cả số đã thêm.

Trung vị: phần tử giữa nếu lẻ, trung bình 2 phần tử giữa nếu chẵn.

Thuật toán: 2 Heap (Priority Queue)

• left (max-heap): nửa nhỏ hơn, đỉnh = lớn nhất nửa trái.
• right (min-heap): nửa lớn hơn, đỉnh = nhỏ nhất nửa phải.
• Duy trì: left.size() == right.size() hoặc left.size() == right.size() + 1.

Thao tác

addNum(num)

if left empty or num < left.top(): push left
else: push right

// Cân bằng
if left.size() < right.size(): move right.top() to left
if left.size() - right.size() > 1: move left.top() to right

findMedian()

if left.size() > right.size(): return left.top()
else: return (left.top() + right.top()) / 2.0

Cài đặt 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() {
        if (left.size() > right.size()) return left.top();
        return (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
    return 0;
}

Độ phức tạp

• addNum: O(log n).
• findMedian: O(1).
• Không gian: O(n).

Input / Output

addNum(10); addNum(15); findMedian() → 12.5
addNum(25); addNum(30); findMedian() → 20
addNum(40); findMedian() → 25