std::priority_queue 是在 C++98 标准中引入的。C++98 是第一个官方批准的 C++ 标准，它在很大程度上奠定了 C++ 语言的基础，并引入了 STL（Standard Template Library），STL 包括了一系列标准的模板类和函数，用于处理数据结构和算法操作。
std::priority_queue 是 STL 的一部分，作为一种容器适配器，它提供了对优先队列这种数据结构的支持。自从 C++98 标准之后，std::priority_queue 一直是 C++ 标准库的一部分，并在后续的 C++ 标准中得到保留和维护。
1. std::priority_queue 的构造方式
std::priority_queue 在 C++ 标准库中提供了几种不同的构造方式。这些构造方法允许你创建一个优先队列，并根据需要自定义底层容器和比较函数。下面是 std::priority_queue 的几种主要构造方法：
1. 默认构造函数
这是最常用的构造函数，它创建一个空的优先队列。默认情况下，底层容器是 std::vector，比较函数是 std::less<T>，其中 T 是存储在优先队列中的元素类型。
std::priority_queue<int> pq;
2. 使用自定义比较函数
此构造函数允许你使用自定义的比较函数。例如，你可以使用 std::greater<T> 来创建一个最小堆。
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
3. 从范围构造
这个构造函数允许你从一个现有范围（例如另一个容器）中创建一个优先队列。你需要提供开始和结束迭代器，以及可选的比较函数和容器。
std::vector<int> vec = {1, 2, 3, 4, 5}; std::priority_queue<int> pq(vec.begin(), vec.end());
4. 使用自定义底层容器和比较函数
你可以指定一个自定义的底层容器和比较函数。这允许完全控制优先队列的行为。
std::priority_queue<int, std::deque<int>, std::greater<int>> customPQ;
注意事项
- 在使用从范围构造的构造函数时，优先队列会使用提供的迭代器范围中的元素来初始化，并根据比较函数建立堆的属性。
- 自定义比较函数应该是一个能够确定两个元素优先级的二元谓词。
- 自定义底层容器需要支持
front(),push_back(),pop_back()以及随机访问迭代器。
通过这些不同的构造方法，std::priority_queue 提供了很大的灵活性，使得它可以适应各种不同的使用场景。
2. std::priority_queue 的push和pop
std::priority_queue 是 C++ 标准库中的一个容器适配器，用于提供优先队列的功能。它基于某种底层容器（默认是 std::vector）和一个比较函数（默认是 std::less，意味着元素将按最大值优先的顺序排列）。在 std::priority_queue 中，最大（或根据比较函数确定的“最高优先级”）的元素总是位于队列的前面。
插入（push）
- 用法：
void push(const T& value);或void push(T&& value); - 描述：将一个新元素添加到优先队列中。新元素被放置在优先队列的末尾，然后根据其优先级进行上浮，以确保队列的顶部总是具有最高优先级的元素。
- 复杂度：通常是对数时间，具体取决于底层容器的性能特性。
取出（pop）
- 用法：
void pop(); - 描述：移除优先队列中优先级最高的元素。这通常是队列的第一个元素。
pop操作会将最高优先级的元素移除，然后重新排列剩余元素以保持优先队列的性质。 - 注意：
pop函数不返回被移除的元素。如果你需要访问这个元素，应该先调用top()。 - 复杂度：同样是对数时间，取决于底层容器。
访问顶部元素（top）
- 用法：
const T& top() const;或T& top(); - 描述：返回优先队列中优先级最高的元素的引用。这允许你查看但不移除队列顶部的元素。
- 复杂度：常数时间。
示例代码
#include <iostream> #include <queue> int main() { std::priority_queue<int> pq; // 插入元素 pq.push(10); pq.push(5); pq.push(15); // 显示并移除队列顶部元素 while (!pq.empty()) { std::cout << pq.top() << std::endl; // 显示顶部元素 pq.pop(); // 移除顶部元素 } return 0; }
这个示例中，优先队列将按照元素的降序排列（默认情况），所以首先输出的是最大的元素。
3. std::priority_queue 的优先级详解
在 std::priority_queue 中，优先级的判断是基于元素的值和一个比较函数来实现的。默认情况下，比较函数是 std::less<T>，这意味着较大的元素会被视为具有较高的优先级。因此，在默认配置下的 std::priority_queue 实际上是一个最大堆，即队列的顶部始终是当前最大的元素。
如果你想改变优先级的判断方式，比如想要一个最小堆（队列顶部是最小元素），你可以在声明 std::priority_queue 时指定一个不同的比较函数，例如 std::greater<T>。
举例说明
- 默认情况下（最大堆）:
- 插入元素：10, 5, 15。
- 由于默认使用
std::less<T>，较大的数字具有更高的优先级。 - 因此，15 会是队列的顶部元素。
- 使用
std::greater<T>（最小堆）:
- 如果声明优先队列时使用
std::greater<T>，则较小的数字将具有更高的优先级。 - 插入相同的元素（10, 5, 15）后，5 将是队列的顶部元素。
示例代码：使用 std::greater<T>
#include <iostream> #include <queue> #include <functional> // 对于 std::greater int main() { // 使用 std::greater 来创建最小堆 std::priority_queue<int, std::vector<int>, std::greater<int>> pq; // 插入元素 pq.push(10); pq.push(5); pq.push(15); // 显示并移除队列顶部元素 while (!pq.empty()) { std::cout << pq.top() << std::endl; // 显示顶部元素 pq.pop(); // 移除顶部元素 } return 0; }
在这个示例中，由于使用了 std::greater<int>，所以最小的元素（5）将会是队列的顶部元素。
4 . std::priority_queue 的优缺点
std::priority_queue 是 C++ 标准库中的一个容器适配器，提供了一组特定的功能，使其适用于特定类型的问题。了解其优点和缺点有助于确定何时使用它。
优点
- 高效的元素访问和管理：
std::priority_queue提供了对其顶部元素的快速访问（即优先级最高的元素），这在许多算法中非常有用，例如在贪心算法、图算法（如 Dijkstra 算法）中。 - 自动元素排序：当元素被加入到队列中时，它们会根据给定的比较函数自动排序。这意味着你总是可以快速访问或删除优先级最高的元素。
- 灵活性：通过模板参数，你可以自定义存储的元素类型、底层容器和比较函数，使其适应特定需求。
- 易于使用：与标准库中的其他容器一样，
std::priority_queue提供了清晰、一致的 API，使得它易于理解和使用。
缺点
- 有限的接口：
std::priority_queue只提供了对队列顶部元素的访问。它不支持遍历或直接访问除顶部元素之外的其他元素。 - 不支持元素的随机访问：由于其性质，你不能像使用
std::vector那样随机访问或检索优先队列中的元素。 - 不支持修改优先级：一旦元素被加入到
std::priority_queue中，你就不能更改其优先级或直接更新它。要实现这样的功能，需要从队列中移除该元素，修改后再重新加入。 - 内存使用：由于基于底层容器（如
std::vector），std::priority_queue可能会在内存分配上不如某些专用的堆结构高效。 - 不支持迭代器：与大多数其他标准库容器不同，
std::priority_queue不提供迭代器，因此不能用于标准算法库中的函数。
结论
std::priority_queue 非常适合于需要频繁访问和删除优先级最高元素的场景，尤其是在算法中需要这样的操作时。然而，如果你需要更复杂的操作，如元素的随机访问、修改或遍历，那么可能需要考虑其他数据结构。
6. std::priority_queue 适用场景
std::priority_queue 作为一种特殊的队列结构，在 C++ 中主要用于管理一组元素，其中每个元素都有一个优先级。优先队列保证每次取出的元素都是当前优先级最高的。这种特性使得 std::priority_queue 在特定场景下非常有用：
1. 贪心算法
在需要做出局部最优选择的场景中，如在贪心算法中，std::priority_queue 可以用来保持当前可用选项的有序性。例如，在 Huffman 编码和 Dijkstra 的最短路径算法中，优先队列用于选择最小成本或最短路径的节点。
2. 事件驱动的模拟
在事件驱动的模拟（如离散事件模拟）中，事件可以根据它们发生的时间顺序排列在优先队列中。这样可以确保事件按照正确的顺序被处理。
3. 调度算法
在操作系统和任务调度算法中，std::priority_queue 可用于管理不同优先级的任务。例如，处理器时间可以优先分配给优先级最高的任务。
4. 数据流处理
在处理实时数据流，如股票市场数据或社交媒体数据流时，可以用优先队列来跟踪最重要的或最相关的数据项。
5. A* 搜索算法
在路径查找和图搜索算法，特别是 A* 搜索算法中，优先队列用于有效地选择下一个要探索的节点。
6. 优先服务的队列
在需要按优先级处理元素的场景，如客户服务、医疗服务等领域，优先队列可以管理待处理的请求。
7. 堆排序
std::priority_queue 可用于实现堆排序算法，这是一种高效的排序方法，尤其是在处理大数据集时。
注意事项
虽然 std::priority_queue 在这些场景中非常有用，但它也有其限制，如不支持随机访问、不能直接修改元素等。因此，在选择使用它之前，需要考虑这些限制是否会影响到你的应用场景。
7. std::priority_queue 可能的实现
std::priority_queue 在 C++ 中通常是基于堆（heap）数据结构实现的，特别是使用一种称为“二叉堆”的形式。二叉堆是一种完全二叉树，可以有效地支持优先队列的操作。
内部排序算法
- 堆排序算法：
std::priority_queue使用堆排序算法来维护元素的顺序。在最大堆中，父节点的值总是大于或等于其子节点的值；在最小堆中，则总是小于或等于其子节点的值。 - 插入操作（
push）：当新元素被加入时，它首先被放置在堆的末尾（即树的最底层），然后通过一系列的“上浮”操作，将其移动到正确的位置以维护堆的特性。这个过程的时间复杂度是 O(log n)。 - 删除操作（
pop）：移除元素（通常是顶部元素）时，堆会用最后一个元素替换顶部元素，然后执行“下沉”操作，将这个元素下移到正确的位置，以保持堆的特性。这个过程的时间复杂度也是 O(log n)。 - 查找顶部元素（
top）：查找堆顶元素（优先级最高的元素）是一个常数时间操作，即 O(1)。
我将创建一个Markdown表格，展示C++中std::priority_queue（优先队列）的各种操作的时间复杂度。下面是这个表格：
| 操作 | 时间复杂度 |
| 插入 | O(log n) |
| 移除 | O(log n) |
| 查询顶部 | O(1) |
| 查询大小 | O(1) |
| 检查空 | O(1) |
解释：
- 插入：向
std::priority_queue中插入一个元素，通常是将其放在底层容器的末尾，然后进行上浮(heapify up)操作。这个操作的时间复杂度为O(log n)，其中n是优先队列中的元素数量。 - 移除：移除顶部元素（最高优先级的元素）涉及到移除堆的根节点，然后进行下沉(heapify down)操作。这个操作同样需要O(log n)的时间。
- 查询顶部：访问顶部元素（最高优先级的元素）是一个常数时间操作，时间复杂度为O(1)，因为它总是位于底层容器的前端。
- 查询大小：检查
std::priority_queue的大小（它包含的元素数量）是一个常数时间操作。 - 检查空：检查
std::priority_queue是否为空也是一个常数时间操作。
请注意，std::priority_queue不支持直接移除或访问顶部元素以外的元素，因此类似随机访问或删除（顶部元素以外）等操作在此不适用。
性能考虑
- 数据量大时的性能：由于
std::priority_queue的主要操作（插入和删除）具有 O(log n) 的时间复杂度，因此即使在处理大量数据时，它也能保持良好的性能。这使得它适合用于需要频繁插入和删除元素的场景。 - 内存使用：
std::priority_queue的内存使用取决于其底层容器（默认是std::vector）。由于是基于数组的实现，它通常比基于节点的数据结构（如链表）更加内存高效。 - 元素比较：元素的比较次数取决于堆的高度，即 O(log n)。你可以通过提供自定义的比较函数来影响排序行为。这对于处理复杂对象或自定义排序准则特别重要。
总体来说，std::priority_queue 在处理具有动态优先级的数据集合方面非常有效，特别是在需要快速访问、添加或移除优先级最高或最低元素的应用中。然而，它不适用于需要频繁访问或修改队列中间元素的场景。
以下是std::priority_queue数据结构的一个简化的C++实现。这个实现使用了最大堆来存储元素，其中堆的顶部元素（位于数组的第一个位置）是最大的。
#include <vector> #include <iostream> template<typename T> class PriorityQueue { private: std::vector<T> heap; void heapifyUp(int index) { while (index > 0 && heap[(index - 1) / 2] < heap[index]) { std::swap(heap[index], heap[(index - 1) / 2]); index = (index - 1) / 2; } } void heapifyDown(int index) { int size = heap.size(); int largest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < size && heap[left] > heap[largest]) { largest = left; } if (right < size && heap[right] > heap[largest]) { largest = right; } if (largest != index) { std::swap(heap[index], heap[largest]); heapifyDown(largest); } } public: bool isEmpty() const { return heap.empty(); } T top() const { if (!isEmpty()) { return heap.front(); } throw std::out_of_range("PriorityQueue is empty"); } void push(const T& value) { heap.push_back(value); int index = heap.size() - 1; heapifyUp(index); } void pop() { if (isEmpty()) { throw std::out_of_range("PriorityQueue is empty"); } heap[0] = heap.back(); heap.pop_back(); heapifyDown(0); } };
在这个实现中，我们有：
heapifyUp函数，用于在插入元素时调整堆。heapifyDown函数，用于在删除顶部元素后调整堆。push函数，用于添加元素到优先队列。pop函数，用于移除优先级最高的元素。top函数，用于获取优先级最高的元素但不移除它。isEmpty函数，用于检查优先队列是否为空。
请注意，这是一个简化的实现，专门用于教学目的。标准库中的std::priority_queue提供了更复杂的功能和更优的性能。此外，异常处理和边界条件检查在实际应用中应该更加全面。
结语
在我们的编程学习之旅中，理解是我们迈向更高层次的重要一步。然而，掌握新技能、新理念，始终需要时间和坚持。从心理学的角度看，学习往往伴随着不断的试错和调整，这就像是我们的大脑在逐渐优化其解决问题的“算法”。
这就是为什么当我们遇到错误，我们应该将其视为学习和进步的机会，而不仅仅是困扰。通过理解和解决这些问题，我们不仅可以修复当前的代码，更可以提升我们的编程能力，防止在未来的项目中犯相同的错误。
我鼓励大家积极参与进来，不断提升自己的编程技术。无论你是初学者还是有经验的开发者，我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用，不妨点击收藏，或者留下你的评论分享你的见解和经验，也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持，也是对我持续分享和创作的动力。
