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