一. 优先级队列简介
首先，它的本质就是一个堆（heap）。
在C++中，优先级队列（Priority Queue）是一种特殊的容器适配器，它提供了一个能实现类似堆的结构的功能。优先级队列保证了队首元素总是最大的（或者在最小的元素在优先级最高的定义下是最小的），与普通队列不同，优先级队列的出队操作（front和pop）总是取出具有最高优先级的元素，而入队操作（push）会将新元素插入到正确的位置以保持优先级顺序。这种顺序是通过堆这种数据结构来实现的。
在实践中，优先级队列通常用于需要快速检索最大（或最小）元素的场景，例如在图算法中的Dijkstra算法，或者在处理事件时根据事件的优先级来排序。
二. 使用示例
在C++标准库中，优先级队列（std::priority_queue）是在<queue>头文件中定义的。它有以下几个基本操作：
empty()：判断优先级队列是否为空。size()：返回优先级队列中元素的数量。top()：返回队首元素，即优先级最高的元素。push(const T& value)：向优先级队列中添加一个元素,并自动根据优先级排序。pop()：移除并返回队首元素（优先级最高的元素）。 在使用它时要注意，它默认使用 std::less 作为比较函数，这意味着它默认构建的是最大堆。如果你想创建一个最小堆，你可以在创建优先级队列时提供一个不同的比较函数，比如 std::greater 。
下面是一个简单的例子，展示了如何在C++中使用优先级队列：
#include <iostream>#include <queue>int main() { std::priority_queue<int> pq; // 默认创建最大堆 pq.push(1); pq.push(2); pq.push(3); pq.push(4); pq.push(5); while (!pq.empty()) { std::cout << pq.top() << " "; // 输出:5 4 3 2 1 pq.pop(); } return 0;}创建它时，还可以指定底层元素类型，容器类型（默认为std::vector）以及可选的比较对象。
比如下面的最小堆：
#include <iostream>#include <queue>int main() { std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 创建最小堆 pq.push(5); pq.push(4); pq.push(3); pq.push(2); pq.push(1); while (!pq.empty()) { std::cout << pq.top() << " "; // 输出:1 2 3 4 5 pq.pop(); } return 0;}这样就改变了队列的优先级。
三. 模拟实现 priority_queue
因为优先级队列的底层和 堆 的实现逻辑相同，所以得先实现向上调整算法，和向下调整算法，这里因为要适配优先级队列，所以会稍微有点差别。这里建的是一个大顶堆。
1.堆的写法应该是这样：
// 大顶堆// 向上调整void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (arr[parent] > arr[child]) { swap(c[parent], c[child]); child = parent; parent = (parent - 1) / 2; } else break; }}// 向下调整void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child < c.size()) { if (child + 1 < c.size() && arr[child] > arr[child+1]) child++; if (arr[parent] > arr[child]) { swap(c[parent], c[child]); parent = child; child = child * 2 + 1; } else break; }}而在优先级队列中是这样写的：
template<class T>struct Greater { bool operator()(const T& x, const T& y) { return x > y; }};template<class T>struct Less{ bool operator()(const T& x, const T& y) { return x < y; }};template <class T, class Container = vector<T>, class Compare = less<T> >class priority_queue{public: void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (comp(c[parent], c[child])) { swap(c[parent], c[child]); child = parent; parent = (parent - 1) / 2; } else break; } } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child < c.size()) { if (child + 1 < c.size() && comp(c[child], c[child + 1])) child++; if (comp(c[parent], c[child])) { swap(c[parent], c[child]); parent = child; child = child * 2 + 1; } else break; } } // ......private: Container c; Compare comp;};可以看到这里因为有两个优先级，所以用到了两个重载了 ( ) 操作符的仿函数，使其可以像函数一样被调用，这一点很像C语言中的函数调用。
完整实现代码
#include<vector>using namespace std;namespace pq{ template<class T> struct Greater { bool operator()(const T& x, const T& y) { return x > y; } }; template<class T> struct Less { bool operator()(const T& x, const T& y) { return x < y; } }; // 默认建大顶堆 template <class T, class Container = vector<T>, class Compare = less<T> > class priority_queue { public: priority_queue(){} void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (comp(c[parent], c[child])) { swap(c[parent], c[child]); child = parent; parent = (parent - 1) / 2; } else break; } } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child < c.size()) { if (child + 1 < c.size() && comp(c[child], c[child + 1])) child++; if (comp(c[parent], c[child])) { swap(c[parent], c[child]); parent = child; child = child * 2 + 1; } else break; } } bool empty() const { return c.empty(); } size_t size() const { return c.size(); } T& top() const { if (empty()) return; return c[0]; } void push(const T& x) { c.push_back(x); adjust_up(c.size() - 1); } void pop() { if (empty()) return; swap(c[0], c[c.size() - 1]); c.pop_back(); adjust_down(0); } private: Container c; Compare comp; };}