《灵珠觉醒：从零到算法金仙的C++修炼》卷八·鸿蒙初判（78）乾坤鼎炼堆结构 - 数据流的中位数（双堆维护）

在这篇文章中，我们跟随小哪吒学习了如何使用双堆结构维护数据流的中位数。通过暴力解法的尝试，哪吒意识到直接排序虽然直观，但在数据量较大时效率低下。在太乙真人的指引下，他领悟了双堆结构的精髓，通过最大堆和最小堆的配合，高效地维护了数据流的中位数，大幅减少了时间复杂度。我们还详细介绍了C++中优先队列的基本操作。通过这次修炼，哪吒不仅提升了算法能力，还对双堆结构的应用有了更深刻的理解。

轻口味

1062人浏览 · 2025-03-19 07:53:53

轻口味 · 2025-03-19 07:53:53 发布

《灵珠觉醒：从零到算法金仙的C++修炼》卷八·鸿蒙初判（78）乾坤鼎炼堆结构 - 数据流的中位数（双堆维护）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的乾坤鼎领域，鼎中翻滚着数据流的波涛，代表着动态数据处理的奥秘。领域的入口处有一块巨大的石碑，上面刻着一行文字：“欲炼此鼎，需以乾坤之力，双堆维护，数据流中位数显真身。”

哪吒定睛一看，石碑上还有一行小字：“当数据流为1, 2, 3, 4, 5时，中位数序列应为1, 1.5, 2, 2.5, 3。”哪吒心中一动，他知道这是一道关于数据流中位数的难题，需要通过双堆结构来解决。

暴力解法：乾坤鼎领域的初次尝试

哪吒心想：“要找到数据流的中位数，我可以尝试将所有数据存储起来，每次插入新数据后进行排序，然后找到中间的值。”他催动乾坤鼎之力，通过动态数组存储数据，并在每次插入后排序，试图得到中位数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class MedianFinder {
private:
    vector<int> data;

public:
    void addNum(int num) {
        data.push_back(num);
    }

    double findMedian() {
        sort(data.begin(), data.end());
        int n = data.size();
        if (n % 2 == 1) {
            return data[n / 2];
        } else {
            return (data[n / 2 - 1] + data[n / 2]) / 2.0;
        }
    }
};

int main() {
    MedianFinder mf;
    mf.addNum(1);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(2);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(3);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(4);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(5);
    cout << "中位数：" << mf.findMedian() << endl;
    return 0;
}

哪吒成功地得到了中位数，但乾坤鼎领域的光芒却黯淡了下来。他意识到，这种方法在每次插入后都需要排序，时间复杂度高达O(n log n)，在数据量较大时，灵力消耗巨大。

C++语法点

在C++中，双堆的实现涉及到优先队列。以下是一些重要特性：

优先队列：
- 使用priority_queue容器适配器实现堆结构。
- 默认为最大堆，可通过greater<int>实现最小堆。
堆操作：
- 使用push、pop和top方法操作堆。

高阶优化：双堆维护的智慧

哪吒元神中突然浮现金色铭文——「乾坤鼎炼堆结构，数据流中位数显真身」。他领悟到，可以通过双堆结构，维护一个最大堆和一个最小堆，分别存储数据流的较小部分和较大部分，从而高效地找到中位数。

哪吒决定使用最大堆和最小堆，将数据流分为两部分。最大堆存储较小的部分，最小堆存储较大的部分。通过这种方式，他成功地将插入和查找中位数的时间复杂度降低到O(log n)和O(1)，大幅减少了灵力消耗。

#include <iostream>
#include <queue>

using namespace std;

class MedianFinder {
private:
    priority_queue<int> maxHeap; // 存储较小的部分
    priority_queue<int, vector<int>, greater<int>> minHeap; // 存储较大的部分

public:
    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();
        } else {
            return (maxHeap.top() + minHeap.top()) / 2.0;
        }
    }
};

int main() {
    MedianFinder mf;
    mf.addNum(1);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(2);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(3);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(4);
    cout << "中位数：" << mf.findMedian() << endl;
    mf.addNum(5);
    cout << "中位数：" << mf.findMedian() << endl;
    return 0;
}