C++ Priority Queue

在 C++ 中，优先级队列是 STL 中一个派生的容器，它只考虑最高优先级的元素。普通队列遵循 FIFO（先进先出）策略，而优先级队列则根据优先级弹出元素，即最高优先级的元素首先被弹出。

在某些方面，它与普通队列相似，但在以下方面有所不同：

• 与普通队列中所有元素都被平等对待不同，优先级队列中的每个元素都有一个关联的优先级。
• 在优先级队列中，优先级最高的元素会先被移除，而队列遵循 FIFO（先进先出）策略，这意味着最先插入的元素会最先被删除。
• 如果存在多个具有相同优先级的元素，则会考虑队列中元素的顺序。

语法

它具有以下语法：

在这个语法中，

• int： 这是元素的类型。
• variable_name： 这是变量的名称。

优先级队列容器提供了二叉堆数据结构的内置实现。这些可以是两种类型的堆。

1）最大堆优先级队列（默认）

在最大堆优先级队列中，值最大的元素拥有最高的优先级，并最先被访问。这是 C++ 中 std::priority_queue 的默认行为。

语法

它具有以下语法：

在这个语法中，

• data_type： 它代表存储在优先级队列中的元素。

最大堆优先级队列示例

让我们举一个简单的例子来说明 C++ 中的最大堆优先级队列。

输出

Elements in max-heap order: 30 20 10 5

说明

在此示例中，priority_queue<int> 内部使用 std::less<int>。最大的元素（30）具有最高的优先级。元素按值递减的顺序打印。

2）最小堆优先级队列（自定义比较器）

在最小堆优先级队列中，值最小的元素拥有最高的优先级，并最先被访问。我们可以使用自定义比较器（如 std::greater）来实现这一点。

语法

它具有以下语法：

在这个语法中，

• Vector<int>： 它代表 STL 容器。
• greater<int>： 它代表比较器类。

最小堆优先级队列示例

让我们举一个例子来说明 C++ 中优先级队列的最小堆。

输出

Elements in min-heap order: 5 10 20 30

说明

第三个模板参数 std::greater<int> 将行为更改为最小堆。最小的元素（5）获得最高的优先级。元素按值递增的顺序打印。

让我们通过一个简单的例子来理解优先级队列。

在上面的说明中，我们使用 push() 函数插入了元素，插入操作与普通队列相同。但是，当我们使用 pop() 函数从队列中删除元素时，优先级最高的元素将被首先删除。

优先级队列的基本操作

C++ 中优先级队列的几个基本操作如下：

1）插入元素

在优先级队列中，push() 方法用于插入元素。由于它会自动将最重要的方面（默认情况下是最大的）置于顶部，因此在每次插入过程中，堆属性都会保持不变。

2）访问顶部元素

top() 函数根据其默认的最大值优先级从优先级队列中提取最大元素。优先级队列允许用户以 O(1) 的恒定时间操作访问最大元素，而无需删除它。top() 函数使我们能够在执行 pop() 函数等操作之前查看最大值。

插入和访问顶部元素示例

让我们举一个例子来说明如何在优先级队列中插入和访问元素。

输出

Maximum element: 90

说明

在此示例中，优先级队列按此顺序接收元素 70、60、90 和 55。由于 max-heap 排序，90 自动成为顶部元素。pq.top() 的正确执行返回 90，因为队列在其操作中实现了元素优先级排序。

3）删除顶部元素

pop() 函数用于根据优先级级别删除优先级队列前端（顶部元素）。用户应首先使用 top() 函数检索被删除的元素，因为 pop() 不返回任何对象。队列系统处理下一个最大的元素，该元素会自动占据顶部选择的位置。

优先级队列中删除顶部元素示例

让我们举一个例子来说明如何删除优先级队列中的顶部元素。

输出

Before pop, top: 35
After pop, new top: 25

说明

priority_queue 接收元素 15、35 和 25。在执行 pop() 函数之前，由于其大小最大，priority_queue 将 35 作为最高元素。pop() 操作从队列中移除 35，导致 25 成为最高优先级元素。

4）遍历（伪遍历）

优先级队列不像向量或列表那样提供直接的遍历访问。访问所有元素的流程始于 top()，然后立即进行 pop() 操作。由于优先级队列默认作为最大堆结构运行，因此元素的打印顺序是降序的。

优先级队列中的 C++ 遍历示例

让我们举一个例子来说明 C++ 中优先级队列的遍历。

输出

Elements in descending order: 30 20 10

说明

在此示例中，插入了值 20、10 和 30。之后，由于其队列设计，优先级队列的顶部是最大的元素。程序继续处理下一个最大的值 20，然后打印 10。打印顺序对于所有元素都遵循降序。

5）更改优先级队列顺序

C++ 开发者可以通过定义自定义比较器来更改应用程序中的优先级队列顺序。C++ 优先级队列的默认操作建立最大堆行为，使高优先级元素在数据结构中保持较高位置。自定义比较器使我们能够将优先级队列从默认的最大堆类型转换为最小堆或任何自定义优先级方案。

更改优先级队列顺序示例

让我们举一个例子来说明如何在 C++ 中更改优先级队列顺序。

输出

Top element (min-heap): 10

说明

使用 greater<int> 函数将程序中的默认最大堆转换为最小堆。最小堆的顶部包含内部的最小元素。处理队列后，输出显示 10，因为它代表优先级队列中存储的最小元素。

时间复杂度

优先级队列的成员函数

C++ 中优先级队列的几个成员函数如下：

C++ 优先级队列示例

让我们再看一个 C++ 优先级队列的例子。

输出

Elements of p are :
8
7
6
5
Elements of q are :
4
3
2
1

说明

在上面的代码中，我们声明了两个优先级队列，即 p 和 q。我们在 'p' 优先级队列中插入了四个元素，在 'q' 优先级队列中插入了四个元素。插入元素后，我们使用 swap() 函数将 'p' 队列的元素与 'q' 队列交换。

优先级队列的目的

C++ 中优先级队列的几个用途如下：

• 高效的元素访问：优先级队列能够以 O(1) 的恒定时间访问最高优先级项，并在插入和删除操作上以 O(log n) 的对数时间完成。因此，它们在高性能应用程序中表现出色。
• 顺序管理：系统通过重新排序过程自动重新排列元素，以在添加或删除条目后保持优先级不变。
• 支持自定义优先级：优先级队列系统允许用户通过自定义比较器工具创建自己的元素比较方法。
• 在实时处理中有用：实时处理系统在使用优先级队列方面受益最大，因为它们能够快速响应高优先级任务。

结论

总而言之，C++ 优先级队列提供了数据结构，允许开发人员高效地检索最大或最小优先级元素。通过使用 STL 优先级队列，开发人员可以构建用于调度应用程序、查找系统和资源分配过程的堆。优先级队列中插入和删除数据的复杂度为 O(log n)，这使其成为性能敏感型应用程序的理想选择。

C++ 优先级队列选择题

1）C++ 中 priority_queue 的默认行为是什么？

1. 首先返回优先级最低的元素
2. 按插入顺序存储元素
3. 首先返回优先级最高的元素
4. 首先返回最近添加的元素

2）如何改变 C++ priority_queue 的默认行为，使其首先访问最小的元素？

1. 通过使用栈
2. 实现需要自定义比较器。
3. 容器需要在每次新插入后进行手动排序。
4. 这是不可能的。

3）从概念上讲，优先级队列与标准队列有何不同？

1. 优先级队列在其元素存储在一个循环缓冲区结构中。
2. 优先级队列的实现需要链表。
3. 优先级队列系统会消除优先级状态较低的元素。
4. 优先级队列通过优先级排序而不是到达顺序来确定元素处理的顺序。

4）为什么优先级队列在算法设计中很重要？

1. 系统使用优先级队列对优先级项目进行有效的任务管理
2. 它们简化了指针操作
3. 优先级队列在递归系统中起着至关重要的作用。
4. 优先级队列通过其机制实现随机数据存储。

5）比较器在优先级队列中的主要目的是什么？

1. 研究人员将队列存储容量确定为首要目标。
2. 第二个功能允许在插入后对元素进行排序。
3. 该机制有助于决定哪些元素优先。
4. 第三个要求规定了如何指定容器类型。