c++中priority_queue默认为最大堆，基于vector和堆算法实现；最小堆需指定greater比较器；还可用make_heap等底层函数或手动实现堆结构。
在 C++ 中，priority_queue 是标准模板库（STL）提供的容器适配器，底层默认基于 最大堆（max-heap） 实现，使用 std::vector 作为存储结构，并通过 std::make_heap、std::push_heap、std::pop_heap 等算法维护堆性质。你可以直接使用它，也可以手动实现一个最小堆/最大堆来深入理解原理。
用 STL priority_queue 快速实现优先队列
这是最常用、最安全的方式，适用于绝大多数场景：
- 默认是最大堆：顶部元素最大（
top()返回最大值） - 要改成最小堆，需指定比较器：
priority_queue<int vector>, greater<int>></int></int> - 支持的操作：`push()`、`top()`、`pop()`、`empty()`、`size()`，时间复杂度均为 O(log n)
示例代码：
#include <queue>
#include <iostream>
using namespace std;
int main() {
// 最大堆（默认）
priority_queue<int> maxQ;
maxQ.push(3); maxQ.push(1); maxQ.push(4);
cout << maxQ.top() << endl; // 输出 4
// 最小堆
priority_queue<int, vector<int>, greater<int>> minQ;
minQ.push(3); minQ.push(1); minQ.push(4);
cout << minQ.top() << endl; // 输出 1
}
手动实现一个最小堆（数组模拟）
理解堆本质的关键是掌握「完全二叉树的数组表示」和「上浮（sift-up）/下沉（sift-down）」操作：
立即学习“C++免费学习笔记（深入）”；
- 对于下标为
i的节点，左子节点下标 =2*i + 1，右子节点 =2*i + 2，父节点 =(i-1)/2 - 插入时：加到末尾，然后向上调整（与父节点比较并交换，直到满足堆序）
- 弹出堆顶时：把最后一个元素移到堆顶，再向下调整（与较小的子节点交换，直到满足堆序）
简易最小堆实现（不带泛型，便于理解）：
#include <vector>
#include <iostream>
using namespace std;
class MinHeap {
vector<int> heap;
void siftDown(int i) {
int n = heap.size();
while (true) {
int smallest = i;
int left = 2*i + 1, right = 2*i + 2;
if (left < n && heap[left] < heap[smallest]) smallest = left;
if (right < n && heap[right] < heap[smallest]) smallest = right;
if (smallest == i) break;
swap(heap[i], heap[smallest]);
i = smallest;
}
}
void siftUp(int i) {
while (i > 0) {
int parent = (i-1)/2;
if (heap[i] >= heap[parent]) break;
swap(heap[i], heap[parent]);
i = parent;
}
}
public:
void push(int x) {
heap.push_back(x);
siftUp(heap.size()-1);
}
int top() {
return heap.empty() ? -1 : heap[0];
}
void pop() {
if (heap.empty()) return;
heap[0] = heap.back();
heap.pop_back();
if (!heap.empty()) siftDown(0);
}
bool empty() { return heap.empty(); }
};
用 STL 堆算法手写堆操作（更底层）
C++ 提供了原始堆操作函数，可直接在 vector 或数组上构建/维护堆：
-
make_heap(first, last)：将区间转为最大堆 -
push_heap(first, last)：把末尾元素加入已建好的堆（调用前需先 push_back） -
pop_heap(first, last)：把堆顶移到末尾，剩余部分仍是堆（调用后需再 pop_back） - 若要最小堆，传入
greater<t>()</t>作为比较器
示例：
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<int> v = {3, 1, 4, 1, 5};
make_heap(v.begin(), v.end()); // 构建最大堆
cout << v[0] << endl; // 5
v.push_back(2);
push_heap(v.begin(), v.end()); // 插入 2 并调整
cout << v[0] << endl; // 5 还是最大值
pop_heap(v.begin(), v.end()); // 5 移到末尾
v.pop_back(); // 真正删除
cout << v[0] << endl; // 新的最大值
}
常见误区和注意事项
初学堆容易踩坑，这些点值得留意：
-
priority_queue不支持随机访问或遍历，不能像 vector 那样用下标取中间元素 - 修改堆中某个元素后，不会自动重排——必须重新建堆或手动调整（STL 没提供 update 接口）
- 自定义类型需重载
运算符，或显式传入比较函数对象（如 <code>greater<pair>></pair>） - 堆不是排序算法，但可以借助多次 pop 实现堆排序（O(n log n)）
不复杂但容易忽略。
