C++ STL 优先队列基于堆实现，默认最大堆，底层容器为 vector。支持通过模板参数指定比较器以构建小顶堆。核心接口包括 push、top、pop、size、empty，时间复杂度分别为 log n、1、log n、1、1。本文详细说明了优先队列的初始化、基本操作及基于 vector 的模拟实现过程，包含向上调整与向下调整算法逻辑。
priority_queue 是 C++ 标准模板库（STL）中的一个容器适配器，提供了堆数据结构的实现（默认为最大堆）。它在需要高效访问最大/最小元素的场景下非常有用！
如果需要使用小顶堆，可以这样传参
priority_queue<int, vector<int>, greater<int>>
它是默认基于（大顶）堆实现的，例如一颗用数组存储的完全二叉树。
特点总结：
<queue>）我们通过 优先队列 的容器结构应该猜到，它的底层容器是 vector，为什么不取名叫优先维克托呢。
问：为什么底层容器是 vector？ 连续内存结构适合堆的随机访问需求，缓存友好，且动态数组支持高效尾部操作。
问：为什么头文件是 queue？ 作为容器适配器，优先队列在概念上属于队列的一种，与 queue 共用同一头文件，体现了接口的一致性，比如队列的各种接口刚好吻合它的访问、插入、删除行为。
问：为什么叫优先队列而不是优先维克托？ 名称语义分解：
行为本质：
push()，时间复杂度 O(log n)top()，总是获取优先级最高的元素pop()，移除当前最高优先级元素采用：priority_queue<数据类型> 变量名;
我们可以选择默认初始化：
priority_queue<int> V1;
也可以选择范围初始化：
priority_queue<int> V2(arr, arr+n); //或者用另一个容器去初始化 priority_queue<int> V3(V1.begin(),V1.end());
V.push(val);
遵循堆的性质，只能访问堆顶元素
V.top();
V.size();
V.empty();
为空返回 true；不为空返回 false
V.pop();
template <class T, class Container = std::vector<T>>
class priority_queue {
public:
// 构造可以不写，因为可以直接使用 vector
// 函数实现
private:
Container x;
};
既然底层是 vector，我们用缺省参数直接实例化出一个 vector 类型的变量就可以作为底层实现了。
插入元素调用 vector 的接口就行了，这里由于需要满足优先队列的性质（大顶堆），我们还需要在插入之后使用向上调整，保证堆顶（首元素）是最大的。
插入元素：
// 插入数据
void push(const T& data) {
x.push_back(data);
// 向上调整
PushUp(size() - 1);
}
向上调整：
// 向上调整
void PushUp(int child) {
// 父节点
int parent = (child - 1) / 2;
// 如果孩子节点大于父节点，就向上调整交换（根节点可能也需要调整）
while (parent >= 0) {
// 只要进入循环，那么节点下标一定是在合法范围
if (x[child] > x[parent]) {
// 交换
std::swap(x[child], x[parent]);
// 更新孩子、父节点
child = parent;
parent = (child - 1) / 2;
} else break;
}
}
访问第一个元素即可（堆顶元素）
// 访问元素
T top() {
return x[0];
}
// 计算元素个数
size_t size() {
return x.size();
}
// 判断是否为空
bool empty() {
return x.empty();
}
这里的删除调用 vector 的尾删即可。 删除的方法：先交换堆顶 和 尾部元素，再删除，再使用向下调整保证大顶堆的性质。
// 删除堆顶元素
void pop() {
PopDown(size() - 1);
}
向下调整：
// 向下调整
void PopDown(int child) {
// 交换堆顶和末尾元素
std::swap(x[child], x[0]);
// 去尾
x.pop_back();
// 父子节点
int parent = 0;
child = 2 * parent + 1;
// 开始调整（子节点不能超过范围）
while (child < x.size()) {
// 如果右节点大于左节点
if (child + 1 < x.size() && x[child] < x[child + 1]) {
child++;
}
// 如果父节点小于子节点
if (x[parent] < x[child]) {
std::swap(x[parent], x[child]);
// 更新
parent = child;
child = 2 * parent + 1;
} else break;
}
}
void test1_t() {
priority_queue<int> V1;
// 插入元素
V1.push(10);
V1.push(15);
V1.push(5);
V1.push(20);
V1.push(0);
V1.push(25);
// 元素个数
std::cout << V1.size() << std::endl;
// 访问堆顶元素
std::cout << V1.top() << std::endl;
// 出堆顶元素
V1.pop();
// 访问堆顶元素
std::cout << V1.top() << std::endl;
// 判断是否为空
std::cout << V1.empty() << std::endl;
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online