数据结构 - 堆

This post is not yet available in English. Showing the original version.

April 1, 2025

Table of Contents

数据结构-堆

堆(实现优先级队列)

优先级队列是一种特殊的队列，特殊在优先级队列的出队顺序按照事先规定的优先级顺序进行。可以用线性表实现，但每次需要遍历，这样的出队操作复杂度为 O(n)，效率低，因此考虑使用堆来实现优先级队列。堆通常看作是一棵完全二叉树，且某个节点的值总是不大于或不小于其父节点的值。

基本理解

参考的是CSDN的一条教程，很好理解。

堆的插入

每次都是新数据放在数组最后，然后将数据交换以满足堆的性质（最大堆，最小堆）。插入数据 16 为满足最大堆，调整位置，有父节点与孩节点交换。依然没有完全符合最大堆（根节点数据最大），继续调整位置。

堆的节点删除

堆中每次删除都只能删除堆顶元素。实际操作是给最后一个数据的值（最大或最小值，视堆的性质而定）赋值到堆顶，然后调整位置。然后开始不断调整…

构造最大堆

我们从一个例题开始。目前我们有原始数组 a[]={4,1,3,2,16,9,10,14,8,7} 采用顺序存储的方式，对应的完全二叉树如下图：假设数组中有 n 个元素，我们的遍历与调整应该从a[i],此时 i=n/2-1 开始，然后往前推。（即最中间的那个元素），将它看作父节点，去和它的孩子比较（不要和它的父节点比较）。一样的逻辑，不断比较父节点和孩子节点调整，最后做到最大的数在最上面。

推完了如果发现不是最大堆形式，我们就从最初点（ a[0] ）继续交换，对交换后的值继续交换…

最小堆构造与最大堆构造几乎一致，只是比较调整的时候逻辑是最小的换到父节点。

最大堆的插入节点就是在堆的最后，最小值后面添加一个节点，然后沿着数堆上升调整，和堆的插入是一致的。
堆顶节点删除思想：将堆树的最后节点放到根节点，删除最大值，再重新初始化调整比较。逻辑是一样的。

概念

二叉堆

二叉堆是一个用完全二叉树来实现的优先队列结构，支持高效插入与取最值操作。

特点

完全二叉树（除了最后一层，其他层都满，且从左到右填满）
每个结点都满足：
- 最小堆（小根堆）：父节点 ≤ 子节点
- 最大堆（大根堆）：父节点 ≥ 子节点
用数组实现（因为完全二叉树可以用下标映射）

小技巧

父节点下标 i → 左子节点 2i，右子节点 2i+1
子节点 j → 父节点是 j/2（向下取整）
上调插入 push O(log n)，下调删除最值 pop O(log n)，取最值 O(1) 二叉堆是一种隐式数据结构，将元素的逻辑结构蕴含在存储结构中，避免额外的指针空间开销，所以经常用。

多叉堆

多叉堆（d-ary heap）就是一个每个节点有 d 个孩子的堆，也是一种用数组实现的优先队列。

特点

一般是d 叉完全树
小根堆 / 大根堆原则依然成立
结构仍然是数组实现，不过下标关系会变化：

📌 设根节点下标为 0（或 1 视实现而定）：

父节点 i → 子节点范围是：d*i + 1 到 d*i + d
子节点 j→ 父节点是：(j - 1) / d

应用

哈夫曼树的构建。
Dijkstra 最短路径的构建
贪心算法

实现

STL 实现

在 STL 里有一个现成的“优先队列”。

std::priority_queue

本身是一个堆结构封装好的数据结构，默认用的是大根堆，最大值优先。

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

int main() {
    priority_queue<int> pq;

    pq.push(5);
    pq.push(2);
    pq.push(8);

    cout << pq.top() << endl; // 输出 8（最大值）

    pq.pop(); // 删除最大值

    cout << pq.top() << endl; // 输出 5

    return 0;
}

如果想要最小值优先，可以构造优先级队列的时候，传入比较函数。

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

pq.push(5);
pq.push(2);
pq.push(8);

cout << pq.top() << endl; // 输出 2（最小值）

如果想要自定义结构体的优先级，得先写一个比较器（或者lambda表达式等）

struct Node {
    int id, val;
};
struct cmp {
    bool operator()(const Node &a, const Node &b) {
        return a.val > b.val; // 小根堆：val小的优先
    }
};
priority_queue<Node, vector<Node>, cmp> pq;

这里也附上一个lambda表达式的模板，由于 lambda 是匿名类型，而priority_queue 是模板类，所以传参略微复杂。

auto cmp = ![](const pair<int, int> &a, const pair<int, int> &b) {
    return a.second > b.second;  // 小根堆：值小的优先
};

priority_queue<
    pair<int, int>,
    vector<pair<int, int>>,
    decltype(cmp)
> pq(cmp);

为什么要写 decltype(cmp)？

因为 lambda 是匿名类型，必须用 decltype 获取它的类型作为模板参数。
然后把这个比较器传进去初始化构造函数 pq(cmp) 完整用法

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

int main() {
    // 按 second 小的优先（小根堆）
    auto cmp = ![](const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second;
    };

    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        decltype(cmp)
    > pq(cmp);  // 注意要传 cmp 进去！

    pq.push({1, 10});
    pq.push({2, 5});
    pq.push({3, 20});

    while (!pq.empty()) {
        cout << pq.top().first << " " << pq.top().second << endl;
        pq.pop();
    }

    return 0;
}