【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（最大堆）

1. 底层容器的要求：

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

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

2. 迭代器构造的复杂度：

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

3. 自定义比较器：

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

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

priority_queue的使用

成员函数	功能
push	插入元素到队尾（并排序）
pop	弹出队头元素（堆顶元素）
top	访问队头元素（堆顶元素）
size	获取队列中有效元素个数
empty	判断队列是否为空
swap	交换两个队列的内容

priority_queue的模拟实现 

堆的向上调整算法

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

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

1. 逐级向上比较：

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

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

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

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）用于在删除堆顶元素后，维护堆的结构性质（最大堆或最小堆）。其核心思想是：将堆顶元素与其子节点比较，若不满足堆的性质，则与较大的子节点（最大堆）或较小的子节点（最小堆）交换，逐级向下调整，直到满足堆的性质。

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

1. 逐级向下比较：

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

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

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

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

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;};
}