大根堆小根堆

在C++中，priority_queue 是一个基于堆（Heap）实现的容器适配器，默认是一个大根堆。理解大根堆和小根堆是解决许多经典算法问题（如中位数维护、Top K 问题、滑动窗口最大值等）的基础。

（1） 什么是大根堆？（Max Heap）

定义：

• 大根堆是一种特殊的完全二叉树，满足以下特性：
  • 每个节点的值都大于或等于它的子节点的值。
  • 堆顶（根节点）的元素是堆中最大的元素。

📋 示例（大根堆）

       10
      /  \
     8    5
    / \
   3   7

• 每个节点都比其子节点大。
• 堆顶元素是最大值 10。

🔨 C++ 实现大根堆

priority_queue<int> pq;

默认 priority_queue 就是大根堆。

✅ 示例代码（大根堆）

#include <iostream>
#include <queue>
using namespace std;

int main() 
{
    priority_queue<int> pq;  // 默认就是大根堆

    pq.push(3);
    pq.push(10);
    pq.push(5);
    pq.push(8);

    cout << "大根堆元素 (从大到小)：";
    while (!pq.empty()) 
    {
        cout << pq.top() << " "; // 输出最大值
        pq.pop();                // 移除堆顶元素
    }

    return 0;
}

🔹 输出结果：

大根堆元素 (从大到小)：10 8 5 3

（2）什么是小根堆？（Min Heap）

定义：

• 小根堆是一种特殊的完全二叉树，满足以下特性：
  • 每个节点的值都小于或等于它的子节点的值。
  • 堆顶（根节点）的元素是堆中最小的元素。

📋 示例（小根堆）

       3
      / \
     8   5
    / \
  10   7

• 每个节点都比其子节点小。
• 堆顶元素是最小值 3。

🔨 C++ 实现小根堆

使用 greater<int> 作为第三个模板参数来指定小根堆。

priority_queue<int, vector<int>, greater<int>> pq;

✅ 示例代码（小根堆）

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;  // 小根堆

    pq.push(3);
    pq.push(10);
    pq.push(5);
    pq.push(8);

    cout << "小根堆元素 (从小到大)：";
    while (!pq.empty()) {
        cout << pq.top() << " "; // 输出最小值
        pq.pop();                // 移除堆顶元素
    }

    return 0;

🔹 输出结果：

小根堆元素 (从小到大)：3 5 8 10

（3）两者的核心区别

（4）示例场景分析

🌟 中位数维护问题（示例中提到的 small 和 large）

• small (大根堆) —— 保存较小的一半元素，堆顶是较小部分的最大值。
• large (小根堆) —— 保存较大的一半元素，堆顶是较大部分的最小值。

代码逻辑：

• 当插入元素时，先插入 small，然后将 small 的堆顶元素移动到 large，以保持 small 的元素始终较小。
• 如果 large 的元素个数多于 small，再将 large 的堆顶元素移回 small，以维持两堆的平衡。

✅ 示例代码：

#include <iostream>
#include <queue>
using namespace std;

class MedianFinder {
private:
    priority_queue<int> small; // 大根堆，保存较小的一半
    priority_queue<int, vector<int>, greater<int>> large; // 小根堆，保存较大的一半

public:
    void addNum(int num) {
        small.push(num);
        large.push(small.top());
        small.pop();

        if (large.size() > small.size()) {
            small.push(large.top());
            large.pop();
        }
    }

    double findMedian() {
        if (small.size() > large.size()) return small.top();
        return (small.top() + large.top()) / 2.0;
    }
};

int main() {
    MedianFinder mf;
    mf.addNum(3);
    mf.addNum(1);
    cout << "中位数：" << mf.findMedian() << endl; // 输出 2

    mf.addNum(5);
    cout << "中位数：" << mf.findMedian() << endl; // 输出 3

    mf.addNum(4);
    cout << "中位数：" << mf.findMedian() << endl; // 输出 3.5

    return 0;
}

🔹 输出结果：

中位数：2
中位数：3
中位数：3.5

（5）问题：为什么大根堆叫small，小根堆叫large？

🚨 关键在于 堆中存储的元素范围，而不是堆顶元素的数值。

• small（大根堆）：存储的是较小的一半数据，所以取名为 small。
• large（小根堆）：存储的是较大的一半数据，所以取名为 large。

尽管 small 堆的堆顶元素是较小数据中的最大值，large 堆的堆顶元素是较大数据中的最小值，但关键在于各自堆中包含的元素的整体范围。

🔎 举例说明

假设我们要维护一个数据流，当前数据为：

复制编辑数据流：1, 5, 3, 8, 2

按照中位数维护的规则，小于等于中位数的数字进入 small，大于中位数的数字进入 large。

🚀 第一步：插入 1

• small → {1}
• large → {}
• 中位数 = 1

🚀 第二步：插入 5

• small → {1}
• large → {5}
• 中位数 = (1 + 5) / 2 = 3

🚀 第三步：插入 3

• small → {1, 3}（存储较小部分，堆顶是 3）
• large → {5}
• 中位数 = 3

🚀 第四步：插入 8

• small → {1, 3}
• large → {5, 8}（存储较大部分，堆顶是 5）
• 中位数 = (3 + 5) / 2 = 4

🚀 第五步：插入 2

• small → {1, 2, 3}
• large → {5, 8}
• 中位数 = 3

🔎 为什么不能调换堆名？

• 如果把大根堆命名为 large，小根堆命名为 small，就会导致名字和数据的意义混淆。
• 大根堆负责保存的是较小的一半数据，所以称作 small 才更直观。
• 小根堆负责保存的是较大的一半数据，所以称作 large 更合理。

这是一种逻辑上的命名惯例，强调的是数据的范围，而非堆顶元素的数值。

✅ 总结

• ✅ small（大根堆）—— 存储较小的一半数据，堆顶为较小部分的最大值。
• ✅ large（小根堆）—— 存储较大的一半数据，堆顶为较大部分的最小值。

总结

• priority_queue<int> → 默认是大根堆，适合找最大值或维护较小元素的最大边界。
• priority_queue<int, vector<int>, greater<int>> → 创建一个小根堆，适合找最小值或维护较大元素的最小边界。
• 结合大根堆和小根堆是解决中位数维护、Top K 问题等复杂数据结构问题的高效方法。

如需进一步解释或深入探讨具体算法题，欢迎继续提问！😊