C++中priority_queue是基于堆的容器适配器，默认为大顶堆，自动排序并优先弹出最大值；通过std::greater可改为小顶堆；底层使用vector存储，借助push_heap和pop_heap维护堆性质；支持自定义类型，需重载operator
在C++中，priority_queue 是一个基于堆（heap）实现的容器适配器，能够自动将元素按照优先级排序，默认是大顶堆（最大值优先）。它并不像普通队列那样遵循先进先出原则，而是每次取出当前优先级最高的元素。
priority_queue 的基本用法
在 C++ 标准库中，priority_queue 定义在 头文件中。使用方式如下：
默认大顶堆（最大值优先）：
#include #includestd::priority_queue pq;pq.push(10);pq.push(30);pq.push(20);while (!pq.empty()) {std::cout << pq.top() << " "; // 输出：30 20 10pq.pop();}
小顶堆（最小值优先）：
立即学习“C++免费学习笔记（深入）”；
std::priority_queue<int, std::vector, std::greater> pq;
这里第三个模板参数指定比较函数对象，使用 std::greater 实现升序，即最小值在 top。
priority_queue 的底层原理
priority_queue 实际上是一个堆结构的封装，通常基于完全二叉树，使用数组（如 vector）存储。其核心操作依赖于两个算法：
向上调整（push_heap）：插入新元素后，从底部向上调整以维持堆性质。向下调整（pop_heap）：删除堆顶后，将最后一个元素移到顶部，再向下调整。
这些操作的时间复杂度为 O(log n)，而访问堆顶是 O(1)。
C++ STL 中的 priority_queue 默认使用 std::vector 作为底层容器，并通过 std::make_heap、std::push_heap、std::pop_heap 等函数维护堆结构。
自定义数据类型的优先队列
如果要存储自定义类型（如结构体），需要提供比较逻辑。有两种方式：
方法一：重载 operator
struct Person { int age; std::string name; // 重载小于号，用于大顶堆（年龄大的优先） bool operator<(const Person& p) const { return age < p.age; }};std::priority_queue pq;
方法二：自定义比较结构体
struct Compare { bool operator()(const Person& a, const Person& b) { return a.age < b.age; // 大顶堆 }};std::priority_queue<Person, std::vector, Compare> pq;
手动实现一个简单的优先队列
虽然标准库提供了 priority_queue，但理解其手动实现有助于掌握原理。以下是一个简化版的大顶堆实现：
#include #includeclass MaxPriorityQueue {private:std::vector heap;
void sift_up(int idx) { while (idx > 0) { int parent = (idx - 1) / 2; if (heap[idx] <= heap[parent]) break; std::swap(heap[idx], heap[parent]); idx = parent; }}void sift_down(int idx) { int n = heap.size(); while (idx < n) { int left = 2 * idx + 1; int right = 2 * idx + 2; int max_idx = idx; if (left heap[max_idx]) max_idx = left; if (right heap[max_idx]) max_idx = right; if (max_idx == idx) break; std::swap(heap[idx], heap[max_idx]); idx = max_idx; }}
public:void push(int val) {heap.push_back(val);sift_up(heap.size() - 1);}
void pop() { if (heap.empty()) return; std::swap(heap[0], heap.back()); heap.pop_back(); sift_down(0);}int top() { return heap.empty() ? -1 : heap[0]; }bool empty() { return heap.empty(); }
};
这个实现包含了基本的插入、删除和访问操作，使用数组模拟完全二叉树结构，通过 sift_up 和 sift_down 维护堆性质。
基本上就这些。C++ 的 priority_queue 封装得很好，大多数情况下直接使用标准库即可。了解其背后是堆结构，以及如何通过比较函数控制排序方向，就能灵活应对各种优先级调度场景。
以上就是c++++怎么实现一个优先队列_c++优先队列(priority_queue)的原理与实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1488517.html
微信扫一扫 
支付宝扫一扫 
