引言
中位数，作为统计学中的一个基本概念，指的是一组数值按照大小顺序排列后位于中间的数。如果数值个数为奇数，则中位数为中间那个数；如果为偶数，则中位数为中间两个数的平均值。在C++中，寻找一个数的中位数通常意味着我们需要先对这组数进行排序，然后找到中间位置的数。然而，排序操作的时间复杂度通常为O(n log n)，对于大数据集来说可能不够高效。本文将探讨一种在特定情况下（如数据流或动态数据集合）快速估算中位数的策略——使用两个堆（一个最大堆和一个最小堆）来维持数据的平衡，从而实现近似O(log n)的插入和O(1)的中位数查询。
使用两个堆的策略
为了快速找到中位数，我们可以利用两个堆：一个最大堆（存储较小的一半数据）和一个最小堆（存储较大的一半数据）。这样，最大堆的堆顶元素（即最大值）将始终小于等于最小堆的堆顶元素（即最小值），而中位数则根据数据个数的奇偶性分别位于最大堆的堆顶或两个堆顶元素的平均值。
最大堆：用于存储较小的一半数据，堆顶为最大值。 最小堆：用于存储较大的一半数据，堆顶为最小值。
为了保持两个堆的平衡，我们需要确保：
最大堆的大小要么等于最小堆的大小（数据个数为奇数时，中位数在最大堆中），要么比最小堆小1（数据个数为偶数时，中位数是两个堆顶元素的平均值）。 插入新元素时，根据元素值与当前两个堆顶元素的大小关系，将其插入到合适的堆中，并在必要时调整堆的大小以保持平衡。
C++代码实现
以下是一个使用C++标准库中的std::priority_queue来实现上述策略的示例代码：
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
class MedianFinder {
private:
// 最大堆，存储较小的一半数据，使用std::greater<int>使其变为最大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> maxHeap;
// 最小堆，存储较大的一半数据
std::priority_queue<int> minHeap;
public:
/** initialize your data structure here. */
MedianFinder() {}
void addNum(int num) {
// 插入到最大堆中
if (maxHeap.empty() || num <= maxHeap.top()) {
maxHeap.push(num);
} else {
// 插入到最小堆中，并调整堆的大小以保持平衡
minHeap.push(num);
}
// 平衡两个堆的大小
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.push(maxHeap.top());
maxHeap.pop();
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
// 根据数据个数的奇偶性返回中位数
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.top() + minHeap.top()) / 2.0;
} else {
return maxHeap.top();
}
}
};
int main() {
MedianFinder mf;
mf.addNum(1);
mf.addNum(2);
std::cout << "Median is: " << mf.findMedian() << std::endl; // 输出1.5
mf.addNum(3);
std::cout << "Median is: " << mf.findMedian() << std::endl; // 输出2
return 0;
}
代码解析
类定义：
MedianFinder类包含两个私有成员变量maxHeap和minHeap，分别用于存储较小和较大的一半数据。addNum方法：该方法负责将新元素插入到合适的堆中，并在必要时调整堆的大小以保持平衡。findMedian方法：该方法根据数据个数的奇偶性返回中位数。如果两个堆的大小相等，则中位数是两个堆顶元素的平均值；否则，中位数是最大堆的堆顶元素。main函数：用于测试MedianFinder类的功能。
结论
通过上述策略，我们可以在C++中高效地找到数据流或动态数据集合的中位数。这种方法的关键在于使用两个堆来维持数据的平衡，从而实现快速的插入和中位数查询操作。虽然这种方法在插入元素时需要O(log n)的时间复杂度，但中位数查询的时间复杂度为O(1)，这在处理大数据集或实时数据流时非常有用。
