堆(Heap)

声明大根堆与小根堆

#include<queue>
using namespace std;
int main(){
    priority_queue<int> q; // 默认声明的是大根堆
    priority_queue<int, vector<int>, greater<int>> q; // 声明一个小根堆
    return 0;
}

常用的操作

C++ 算法竞赛中的堆与优先队列

在算法竞赛里，堆（Heap） 是一种完全二叉树结构，核心特性是能快速取出最值；优先队列（priority_queue） 是 C++ STL 封装好的堆，不用手写堆，直接用就行，是高频工具。

---

一、堆是什么？

堆分两种： 1. 大根堆：堆顶是最大值 2. 小根堆：堆顶是最小值

满足性质：

• 父节点 ≥ 子节点（大根堆）
• 父节点 ≤ 子节点（小根堆）
• 是完全二叉树，可用数组存储

常用操作（时间复杂度均为 O(log n)）：

• 插入元素
• 删除堆顶
• 取堆顶最值

---

二、STL 优先队列 priority_queue

• q.top() 取堆顶
• q.pop() 删除堆顶
• q.push(x) 插入
• q.empty() 判断是否为空
• q.size() 大小

示例：

priority_queue<int> q;
q.push(3);
q.push(1);
q.push(5);

// 输出 5 3 1
while (!q.empty()) {
    cout << q.top() << ' ';
    q.pop();
}

3. 自定义结构体优先队列

竞赛常需要按某个字段排序，比如结构体 Node 按 val 从小到大：

struct Node {
    int id, val;
    // 重载 < 号
    bool operator<(const Node& other) const {
        return val > other.val; // 这样就是小根堆
    }
};

priority_queue<Node> q;

记住规则：

• return a < b → 大根堆
• return a > b → 小根堆

---

三、常用操作速查表

操作	代码
定义大根堆	priority_queue<int> q;
定义小根堆	priority_queue<int, vector<int>, greater<int>> q;
插入元素	q.push(x);
取堆顶	q.top();
删除堆顶	q.pop();
是否为空	q.empty();
元素个数	q.size();

---

四、堆的经典应用场景

1. Top K 问题 求前 K 大/前 K 小，用堆 O(n log k) 解决。

2. 贪心算法 每次选当前最优（最值），比如 Huffman 编码、合并果子、任务调度。

3. Dijkstra 最短路 用优先队列优化，从 O(n²) 降到 O(m log n)。

4. 动态维护中位数 大根堆存左半部分，小根堆存右半部分。

5. 多路归并 多个有序数组归并，用堆取当前最小。

---

五、手写堆（必要时）

STL 优先队列不支持删除任意元素，某些题必须手写堆。 手写堆常用数组实现，核心是 up（上浮）、down（下沉）。

简单小根堆框架：

int heap[100005], sz;

void up(int u) {
    while (u > 1 && heap[u] < heap[u/2]) {
        swap(heap[u], heap[u/2]);
        u /= 2;
    }
}

void down(int u) {
    int t = u;
    if (u*2 <= sz && heap[u*2] < heap[t]) t = u*2;
    if (u*2+1 <= sz && heap[u*2+1] < heap[t]) t = u*2+1;
    if (t != u) {
        swap(heap[u], heap[t]);
        down(t);
    }
}

void push(int x) {
    heap[++sz] = x;
    up(sz);
}

void pop() {
    heap[1] = heap[sz--];
    down(1);
}

int top() {
    return heap[1];
}

---

六、竞赛小技巧

1. 求最小用小根堆，求最大用大根堆
2. 多关键字排序直接重载结构体 <
3. Dijkstra 必用小根堆优化
4. STL 优先队列不能遍历，要输出只能 pop
5. 遇到“可删除堆”，一般用懒删除：标记失效元素，取到再扔掉

---