【C++】：STL详解——priority_queue类

目录

priority_queue的概念

priority_queue的构造函数

priority_queue的使用

priority_queue的模拟实现 

堆的向上调整算法

堆的向下调整算法

建堆 

自顶向下逐个插入

自底向上批量调整

对比两种方法

 完整实现

---

priority_queue的概念

priority_queue 是 C++ 标准库中的容器适配器，用于实现优先级队列。

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

注意： 默认情况下priority_queue是大堆。

priority_queue的构造函数

方式一： 使用默认的适配器定义优先级队列（默认大堆）

priority_queue<int> q;

方式二：最小堆（自定义比较器）

priority_queue<int, vector<int>, greater<int>> min_pq;

 方式三：从已有容器构造

vector<int> vec = {5, 2, 8, 1}; priority_queue<int> pq(vec.begin(), vec.end());

方式四：自定义容器和比较器 

struct Point { int x; int y; Point(int a, int b) : x(a), y(b) {} }; // 自定义比较器：按点到原点的距离排序 struct CompareDistance { bool operator()(const Point& a, const Point& b) { return (a.x*a.x + a.y*a.y) < (b.x*b.x + b.y*b.y); } }; priority_queue<Point, vector<Point>, CompareDistance> pq; pq.emplace(1, 2); // 距离平方 = 5 pq.emplace(3, 4); // 距离平方 = 25 cout << pq.top().x << "," << pq.top().y; // 输出 3,4（最大堆）

底层容器的要求：

必须支持 front(), push_back(), pop_back() 和随机访问迭代器（如 vector 或 deque）。

错误示例：list 不支持随机访问，不能作为底层容器。

迭代器构造的复杂度：

通过迭代器构造时，时间复杂度为 O(n)（底层调用 make_heap），而非逐个插入的 O(n log n)。

自定义比较器：

比较器需严格遵循严格弱序规则（如 operator< 或 operator>）。

若比较器有状态，需在构造函数中传递其实例。

priority_queue的使用 成员函数功能push插入元素到队尾（并排序）pop弹出队头元素（堆顶元素）top访问队头元素（堆顶元素）size获取队列中有效元素个数empty判断队列是否为空swap交换两个队列的内容 priority_queue的模拟实现  堆的向上调整算法

堆的 向上调整算法（也称为 上浮 或 adjust-up）用于在插入新元素后，维护堆的结构性质（最大堆或最小堆）。其核心思想是：将新插入的节点与其父节点比较，若不满足堆的性质，则交换位置，逐级向上调整，直到满足堆的性质。

算法步骤（以最大堆为例）

逐级向上比较：

计算当前节点的父节点索引：parent = (child - 1) / 2。

若当前节点的值 大于 父节点的值（违反最大堆性质），则交换二者。

将当前节点指针移动到父节点位置，重复上述过程。

终止条件：

当前节点到达根节点（索引为0）。

当前节点的值不再大于父节点的值（堆性质已满足）。

//堆的向上调整（大堆） void AdjustUp(int child) { int parent = (child - 1) / 2; // 通过child计算parent的下标 while (child > 0) // 调整到根结点的位置截止 { if (v[parent] < v[child]) // 孩子结点的值大于父结点的值 { // 将父结点与孩子结点交换 swap(v[child], v[parent]); // 继续向上进行调整 child = parent; parent = (child - 1) / 2; } else //已成堆 { break; } } }

堆的向下调整算法

堆的 向下调整算法（也称为 下沉 或 adjust-down）用于在删除堆顶元素后，维护堆的结构性质（最大堆或最小堆）。其核心思想是：将堆顶元素与其子节点比较，若不满足堆的性质，则与较大的子节点（最大堆）或较小的子节点（最小堆）交换，逐级向下调整，直到满足堆的性质。

算法步骤（以最大堆为例）

逐级向下比较：

从根节点（索引0）开始，计算其左右子节点索引： left_child = 2 * parent + 1 right_child = 2 * parent + 2.

找到左右子节点中的 最大值（最大堆）或 最小值（最小堆）。

若父节点的值 小于 最大子节点的值（违反最大堆性质），则交换二者。

将父节点指针移动到交换后的子节点位置，重复上述过程。

终止条件：

当前节点已是叶子节点（无子节点）。

当前节点的值已满足堆性质（不小于子节点）。

//堆的向下调整（大堆） void AdjustDown(int parent) { // child记录左右孩子中值较大的孩子的下标 int child = 2 * parent + 1; // 先默认其左孩子的值较大 while (child < n) { if (child + 1 < n && v[child] < v[child + 1]) // 右孩子存在并且右孩子比左孩子还大 { // 较大的孩子改为右孩子 child++; } if (v[parent] < v[child])// 左右孩子中较大孩子的值比父结点还大 { // 将父结点与较小的子结点交换 swap(v[child], v[parent]); // 继续向下进行调整 parent = child; child = 2 * parent + 1; } else// 已成堆 { break; } } } 向上调整 (adjust-up)向下调整 (adjust-down)触发操作插入新元素删除堆顶元素起点新插入的节点（堆末尾）堆顶节点方向自底向上自顶向下时间复杂度O(log n)O(log n) 建堆  自顶向下逐个插入

初始化一个空堆。

逐个将元素插入堆的末尾，每次插入后调用 向上调整算法（adjust-up）

vector<int> arr = {3, 1, 4, 1, 5, 9, 2}; vector<int> heap; for (int num : arr) { heap.push_back(num); adjust_up(heap, heap.size() - 1); } 自底向上批量调整

从 最后一个非叶子节点 开始，向前遍历所有节点。

对每个节点执行 向下调整算法（adjust-down）。

最终整个数组变为堆。

void build_max_heap(vector<int>& arr) { int n = arr.size(); // 从最后一个非叶子节点开始（索引为 (n-2)/2 ） for (int i = (n - 2) / 2; i >= 0; i--) { adjust_down(arr, i, n); } }

对比两种方法 自顶向下（逐个插入）自底向上（Floyd算法）时间复杂度O(n log n)O(n)适用场景动态插入数据静态数据批量建堆核心操作向上调整 (sift-up)向下调整 (sift-down)  完整实现 成员函数实现方法push在容器尾部插入元素后进行一次向上调整算法pop将容器头部和尾部元素交换，再将尾部元素删除，最后从根结点开始进行一次向下调整算法top返回容器的第0个元素size返回容器的当前大小empty判断容器是否为空 namespace wh // 防止命名冲突 { template<class T, class Container = std::vector<T>, class Compare = std::less<T>> class priority_queue { private: // 向上调整法 void adjust_up(int child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { if (com(_con[parent],_con[child])) { std::swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } // 向下调整法 void adjust_down(int parent) { Compare com; size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) { ++child; } if (_con[parent] < _con[child]) { std::swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } public: //构造函数 priority_queue() {} //迭代器构造函数 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first, last) { // 向下调整构建堆 for (int i = (_con.size() - 2) / 2; i >= 0; --i) { // 从最后一个节点的父节点开始调整 adjust_down(i); } } void push(const T& x) { _con.push_back(x); // 插入到堆的尾部 adjust_up(_con.size() - 1); // 向上调整法 } void pop() { std::swap(_con[0], _con[_con.size() - 1]); // 堆顶和尾节点互换 _con.pop_back(); // 删除尾节点 adjust_down(0); // 向下调整法 } const T& top() { return _con[0]; } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; }; }