1 std::priority_queue 概述
std::priority_queue 是 C++ 标准库中的一个容器适配器，它提供了一种实现优先队列数据结构的机制。优先队列是一种特殊的队列，其中元素的出队顺序不是基于它们进入队列的顺序，而是基于它们的优先级。优先级最高的元素将首先被出队。
基本概念
- 队列（Queue）：一种先进先出（FIFO）的数据结构，元素在队列尾部入队，在队列头部出队。
- 优先队列（Priority Queue）：与普通队列不同，优先队列中的元素按照优先级排序，优先级最高的元素先出队。
std::priority_queue 的特点
- 容器适配器：std::priority_queue 是一个容器适配器，这意味着它基于其他容器（如 std::vector 或 std::deque）来实现其功能。默认情况下，std::priority_queue 使用 std::vector 作为底层容器。
- 内部排序：优先队列本质上是一个堆（heap）实现，通常是大顶堆（最大堆），其中父节点的值总是大于或等于其子节点的值。这使得最高优先级的元素总是位于堆的顶部，从而可以快速地获取和删除。
- 自定义优先级：可以通过提供自定义的比较函数或对象来定义元素的优先级。默认情况下，std::priority_queue 使用 std::less 作为比较函数，这意味着元素按照从大到小的顺序排列。如果需要按照从小到大的顺序排列，可以使用 std::greater。
1.1 std::priority_queue 的内部实现
std::priority_queue 的内部实现基于一种特殊的数据结构，通常是大顶堆（max heap），它允许我们快速地访问、插入和删除最大元素。大顶堆是一种完全二叉树，它满足每个节点的值都大于或等于其子节点的值。这使得根节点（堆顶）总是包含堆中的最大元素。
堆的基本性质
- 完全二叉树：堆通常使用数组来实现，这样可以有效地利用空间。数组中的元素按照完全二叉树的层序遍历顺序存储。
- 堆序性：对于大顶堆，父节点的值总是大于或等于其子节点的值。对于小顶堆，父节点的值总是小于或等于其子节点的值。
优先队列的基本操作
- 插入操作（push）
-
- 将新元素添加到数组的末尾。
-
- 从新元素开始，向上调整堆，确保堆的性质得以维持。这个过程称为“上浮”（percolate up）或“上滤”（sift up）。
- 删除操作（pop）
-
- 删除数组的第一个元素（即堆顶元素）。
-
- 将数组的最后一个元素移动到数组的第一个位置。
-
- 从新的堆顶元素开始，向下调整堆，确保堆的性质得以维持。这个过程称为“下沉”（percolate down）或“下滤”（sift down）。
- 获取最大元素（top）
-
- 直接返回数组的第一个元素，即堆顶元素。
内部实现的细节
（1）数组表示
堆通常使用数组来存储元素，因为数组可以通过索引快速访问任意位置的元素。在数组中，对于任意位置 i 的元素，其父节点的位置是 (i - 1) / 2，左子节点的位置是 2 * i + 1，右子节点的位置是 2 * i + 2。
（2）上浮操作（percolate up）
当插入新元素时，我们需要从新元素开始，与其父节点比较。如果新元素大于其父节点，就交换它们的位置，并继续向上比较，直到满足堆的性质或到达堆顶。
（3）下沉操作（percolate down）
当删除堆顶元素时，我们需要从新的堆顶元素开始，与其子节点比较。如果新的堆顶元素小于其任一子节点，就将其与较大的子节点交换位置，并继续向下比较，直到满足堆的性质或没有子节点。
自定义比较函数
std::priority_queue 允许自定义一个比较函数或对象来定义元素的优先级。通过修改比较函数，可以实现小顶堆或其他基于优先级的排序方式。
1.2 std::priority_queue 的性能特点
std::priority_queue 的性能特点主要体现在其基于堆（heap）数据结构实现的特性上。堆是一种特殊的树形数据结构，它满足堆属性：父节点的值总是大于或等于（大顶堆）或小于或等于（小顶堆）其子节点的值。这种特性使得 std::priority_queue 在处理优先级相关的操作时具有高效的性能。
（1）插入操作（push）
对于插入操作，std::priority_queue 的时间复杂度为 O(log n)，其中 n 是队列中元素的数量。这是因为当新元素被添加到队列时，它可能会被放置在数组的末尾，然后需要通过上浮操作（percolate up）来调整堆的结构，确保堆的属性得以维持。上浮操作涉及的比较和交换次数与树的高度相关，对于完全二叉树（即堆），其高度为 O(log n)。
（2）删除操作（pop）
删除操作，特别是删除最大元素（对于大顶堆）或最小元素（对于小顶堆），在 std::priority_queue 中同样具有高效性能。时间复杂度也为 O(log n)。这是因为删除操作涉及将堆顶元素移除，并用堆的最后一个元素替换它，然后通过下沉操作（percolate down）来调整堆的结构。下沉操作同样涉及与树高度相关的比较和交换次数。
（3）访问最大（或最小）元素
访问最大（或最小）元素的操作在 std::priority_queue 中非常高效，时间复杂度为 O(1)。这是因为最大（或最小）元素总是存储在堆顶（即数组的第一个位置），可以直接通过引用或值的方式访问，无需遍历整个数据结构。
（4）自定义比较函数
std::priority_queue 允许通过提供自定义的比较函数或对象来定义元素的优先级。这使得优先队列能够灵活地适应各种应用场景，而不仅仅是基于简单的数值大小进行排序。然而，自定义比较函数本身并不会直接影响 std::priority_queue 的性能，它主要影响队列中元素的排序方式。
（5）空间复杂度
空间复杂度方面，std::priority_queue 主要使用底层容器（如 std::vector）来存储元素。因此，其空间复杂度与底层容器的空间复杂度相同，通常为 O(n)，其中 n 是队列中元素的数量。需要注意的是，由于堆的特性，std::priority_queue 在存储元素时可能会有一些空间浪费，因为底层容器可能需要预留额外的空间以适应可能的增长。
总结来说，std::priority_queue 的性能特点主要体现在其高效的插入、删除和访问最大（或最小）元素操作上。这些操作的时间复杂度都与堆的高度相关，即 O(log n)，使得优先队列在处理大量数据时能够保持较好的性能。同时，通过自定义比较函数，std::priority_queue 能够适应各种优先级排序需求。
2 std::priority_queue 的基本使用
2.1 std::priority_queue 的声明与初始化
声明
首先，需要包含<queue>头文件以使用 std::priority_queue：
#include <queue>
#include <string>
// 声明一个整数类型的 priority_queue
std::priority_queue<int> vals;
// 声明一个字符串类型 priority_queue
std::priority_queue<std::string> strs;
// 声明一个自定义类型的 priority_queue
struct MyStruct
{
int id;
std::string name;
};
std::priority_queue<MyStruct> myStructs;
初始化
可以使用多种方法来初始化 std::priority_queue。
（1）默认初始化：
如果不提供任何参数，std::priority_queue 会使用默认构造函数进行初始化。
std::priority_queue<int> pq;
（2）复制另一个队列：
可以使用另一个 std::priority_queue 的副本来初始化一个新的队列。
std::priority_queue<int> pq1;
pq1.push(3);
pq1.push(1);
pq1.push(4);
std::priority_queue<int> pq2(pq1); // 拷贝构造函数
（3）移动另一个队列：
C++11 及更高版本还支持移动语义，这意味着可以转移另一个队列的内容来初始化新的队列，而不需要复制元素。
std::priority_queue<int> pq1;
pq1.push(3);
pq1.push(1);
pq1.push(4);
std::priority_queue<int> pq2(std::move(pq1)); // 使用 pq1 的内容（通过移动）初始化 pq2，pq1 现在为空
（4）自定义比较函数或对象：
还可以提供自定义的比较函数或对象来初始化 std::priority_queue，以定义元素的优先级：
#include <iostream>
#include <queue>
// 使用自定义的比较类
struct Compare {
bool operator()(const int& a, const int& b) const {
return a > b;
}
};
int main()
{
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
while (!pq.empty())
{
std::cout<< pq.top() <<" ";
pq.pop();
}
std::cout << std::endl;
std::priority_queue<int, std::vector<int>, Compare> pqCustomCompare;
pqCustomCompare.push(3);
pqCustomCompare.push(1);
pqCustomCompare.push(4);
while (!pqCustomCompare.empty())
{
std::cout << pqCustomCompare.top() << " ";
pqCustomCompare.pop();
}
std::cout << std::endl;
return 0;
}
上面代码的输出为：
4 3 1
1 3 4
2.2 std::priority_queue 的大小与容量
（1）大小（size）
std::priority_queue 的大小是指队列中当前存储的元素数量。可以使用 std::priority_queue 的 size 成员函数来获取队列的大小。例如：
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::size_t size = pq.size(); // size 现在是 3，因为队列中有 3 个元素
这个例子向队列中添加了三个元素，并使用 size 成员函数获取队列的大小。
（2）容量（capacity）
与 std::vector 或 std::deque 不同，std::priority_queue 没有直接提供获取其“容量”的成员函数。容量通常指的是容器在不进行内存重新分配的情况下可以容纳的元素数量。由于 std::priority_queue 的设计是为了提供队列操作的接口，并且隐藏了其底层容器的实现细节，因此它并不直接暴露底层容器的容量信息。
2.3 std::priority_queue 的构造函数与析构函数
（1）构造函数
std::priority_queue 提供了多个构造函数，以便在不同的情况下灵活地初始化队列。以下是一些主要的构造函数：
默认构造函数：
std::priority_queue<Type> pq;
此构造函数创建一个空的队列，其底层容器使用默认构造函数进行初始化。这里的 Type 是队列中元素的类型。
拷贝构造函数：
std::priority_queue<Type> pq1(pq2);
此构造函数使用另一个队列 pq2 的内容来初始化新的队列 pq1。它复制 pq2 中的所有元素到 pq1 中。
移动构造函数（C++11 及更高版本）：
std::priority_queue<Type> pq1(std::move(pq2));
此构造函数通过移动另一个队列 pq2 的内容来初始化新的队列 pq1。这意味着 pq2 在移动操作后不再包含其原始元素，这些元素的所有权现在属于 pq1。使用移动构造函数通常比使用拷贝构造函数更高效，因为它可以避免不必要的元素复制。
（2）析构函数
当 std::priority_queue 对象的生命周期结束时，其析构函数会被自动调用。析构函数负责清理队列所占用的资源，包括释放底层容器的内存。注意不需要显式地调用析构函数，因为 C++ 的自动存储期管理会处理这些细节。
例如：
{
std::priority_queue<int> pq;
// ... 在这里使用队列 ...
} // 在这里，当 pq 离开其作用域时，其析构函数会自动被调用
在上面的代码中，当 pq 离开其作用域时，其析构函数会被自动调用，从而释放队列所占用的资源。
3 std::priority_queue 的元素操作
3.1 入队列操作（push）
入队列操作使用 push 成员函数，它接受一个参数，即要添加到队列顶的元素。例如：
std::priority_queue<int> pq;
pq.push(1); // 将整数 1 压入队列中
pq.push(2); // 将整数 2 压入队列中
这个例子创建了一个 int 类型的队列 pq，并使用 push 函数将两个整数依次压入队列中。
3.2 出队列操作（pop）
出队列操作使用 pop 成员函数，它移除队列顶的元素，但不返回该元素的值。例如：
std::priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.pop(); // 移除队列顶元素 2，但不返回它
这个例子创建了一个队列 pq 并压入两个整数。然后，使用 pop 函数移除了队列头部的元素 2。
3.3 查看队列头部元素（top）
查看队列头部元素使用 top 成员函数，它返回队列头部元素的引用，但不移除该元素。例如：
std::priority_queue<int> pq;
pq.push(1);
pq.push(2);
int topElement = pq.top(); // 获取队列头部元素，此时 topElement 的值为 2
这个例子创建了一个队列 pq 并压入两个整数。然后，使用 top 函数获取了队列头部的元素，并将其值存储在 topElement 变量中。
3.4 检查队列是否为空（empty）
检查队列是否为空使用 empty 成员函数，如果队列为空，则返回 true；否则返回 false。例如：
std::priority_queue<int> pq;
bool isEmpty = pq.empty(); // isEmpty 的值为 true，因为队列是空的
pq.push(1);
isEmpty = pq.empty(); // isEmpty 的值为 false，因为队列不再为空
这个例子首先创建了一个空的队列 pq，并使用 empty 函数检查其是否为空。然后，压入一个整数并再次检查队列是否为空。
3.5 队列的交换（swap）
可以使用 swap 成员函数来交换两个队列的内容。例如：
std::priority_queue<int> pq1, pq2;
pq1.push(1);
pq1.push(2);
pq2.push(3);
pq2.push(4);
pq1.swap(pq2); // 交换 pq1 和 pq2 的内容
在这个例子中，pq1 原本包含元素 2 和 1，pq2 包含元素 4 和 3。调用 swap 后，pq1 将包含元素 4 和 3，而 pq2 将包含元素 2 和 1。
4 std::priority_queue 的删除操作
std::priority_queue 设计初衷是提供基本的队列操作，如 push（压入元素）、pop（弹出元素）、top（查看队列顶元素）等。然而，std::priority_queue 并没有直接提供删除队列中特定元素的操作，这是因为它保持了队列的简单性和一致性。
如果需要删除队列中的特定元素，那么可能需要考虑其他的数据结构，如 std::deque 或 std::list，它们提供了更多的元素操作功能。但如果仍然想要使用 std::priority_queue 并删除其中的元素，那么可以通过以下方式间接实现：
（1）弹出元素直到找到并删除目标元素：
可以通过连续调用 pop 函数，直到找到并删除目标元素。但是，这种方法会破坏队列的结构，因为它会移除队列顶的所有元素，直到找到目标元素为止。这通常不是推荐的做法。
std::priority_queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
std::priority_queue<int> pqTmp;
int target = 3;
bool found = false;
while (!pq.empty()) {
int top = pq.top();
pq.pop();
if (top != target) {
pqTmp.push(top); // 将非目标元素重新压入队列中
}
}
pq.swap(pqTmp);
这个例子试图删除值为 3 的元素。通过循环不断地从队列顶弹出元素，检查它是否是想要删除的目标，如果不是，则将其重新压入备用队列中。这种方法效率很低，特别是当队列很大且目标元素靠近队列底时。
（2）使用其他数据结构辅助：
另一种方法是使用一个辅助的数据结构（如 std::vector 或 std::deque）来存储队列中的元素，然后在这个辅助数据结构中删除目标元素，最后再将辅助数据结构中的元素重新压入队列中。这种方法同样会破坏队列的结构，并且效率也不高。
（3）避免需要删除操作：
最好的方法是避免在 std::priority_queue 中进行删除操作。在设计程序时，尽量确保你不需要从队列中删除特定的元素。如果确实需要这种功能，那么可能需要考虑使用其他更适合的数据结构。