295. 数据流的中位数c++

要找出数据流的中位数，可以使用两个优先队列（堆）来实现。一个小顶堆存储较大的一半数据，一个大顶堆存储较小的一半数据。

具体步骤如下：

1. 初始化两个堆，一个小顶堆 `minHeap` 和一个大顶堆 `maxHeap`。
2. 遍历数据流中的每个元素：
- 如果 `minHeap` 和 `maxHeap` 的大小相等，将元素插入到 `maxHeap` 中。
- 如果 `minHeap` 的大小大于 `maxHeap`，将元素插入到 `minHeap` 中。
- 如果插入元素后，`minHeap` 的堆顶元素大于 `maxHeap` 的堆顶元素，则交换两个堆顶元素。
3. 如果两个堆的大小之和是偶数，中位数就是两个堆顶元素的平均值；如果是奇数，中位数就是 `minHeap` 的堆顶元素。

下面是使用 C++ 实现的代码示例：

#include <iostream>
#include <queue>
#include <vector>

class MedianFinder {
public:
    void addNum(int num) {
        if (minHeap.empty() || num > minHeap.top()) {
            minHeap.push(num);
        } else {
            maxHeap.push(num);
        }

        if (minHeap.size() > maxHeap.size() + 1) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        } else if (maxHeap.size() > minHeap.size()) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        }
    }

    double findMedian() {
        if (minHeap.size() == maxHeap.size()) {
            return (minHeap.top() + maxHeap.top()) / 2.0;
        } else {
            return minHeap.top();
        }
    }

private:
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    std::priority_queue<int, std::vector<int>, std::less<int>> maxHeap;
};

int main() {
    MedianFinder finder;
    finder.addNum(1);
    finder.addNum(2);
    std::cout << finder.findMedian() << std::endl;  // 输出 1.5
    finder.addNum(3);
    std::cout << finder.findMedian() << std::endl;  // 输出 2

    return 0;
}

这段代码创建了一个 `MedianFinder` 类，通过 `addNum` 方法添加数据，然后通过 `findMedian` 方法获取中位数。在示例中，数据流为 1、2、3，所以中位数依次为 1.5 和 2。