当前位置：首页 > article >正文

【STL】priority_queue 基础，应用与操作

article 2024/9/20 12:40:40

c在C++的标准模板库（STL）中，priority_queue 是一个基于堆的容器适配器，用于实现优先级队列。它本质上是一个最大堆（Max-Heap），即每次取出元素时，始终取出优先级最高的元素。本文将详细讲解priority_queue的基础操作、特性及使用注意事项。

1. priority_queue的基本概念

priority_queue 是一个容器适配器，通常底层使用 vector 和堆（默认是最大堆）来实现。队列中元素按照优先级排序，默认情况下，优先级最高的元素会被优先弹出。这意味着，容器中第一个元素始终是值最大的。

1.1 头文件

要使用 priority_queue，必须包含头文件：

#include <queue>

1.2 基本定义

std::priority_queue<int> pq;  // 定义一个存储 int 类型的优先级队列（默认最大堆）

1.3 底层容器选择

priority_queue 可以选择不同的底层容器，常用的包括 vector 和 deque，默认情况下是使用 vector。

2. priority_queue 的基本操作

2.1 push() 插入元素

使用 push() 向队列中插入新元素。插入时，元素会根据优先级被放置到合适的位置。

pq.push(5);   // 插入元素 5
pq.push(10);  // 插入元素 10
pq.push(3);   // 插入元素 3

在插入后，priority_queue 会自动调整，使得最大元素始终位于队列顶端。

2.2 top() 获取最大元素

使用 top() 来访问队列中优先级最高的元素（即最大元素）。这个操作不会移除元素，只是返回它的值。

std::cout << pq.top();  // 输出 10

2.3 pop() 移除最大元素

使用 pop() 来移除队列中优先级最高的元素。请注意，这个操作并不返回被移除的元素，仅仅是将其从队列中删除。

pq.pop();  // 移除优先级最高的元素（10）

2.4 empty() 检查队列是否为空

使用 empty() 可以检查优先级队列是否为空，返回一个布尔值。

if (pq.empty()) 
{
    std::cout << "Queue is empty." << std::endl;
}

2.5 size() 返回队列的元素个数

使用 size() 可以返回当前队列中元素的个数。

std::cout << pq.size();  // 输出当前队列中元素的个数

3. 自定义比较函数（最小堆）

默认情况下，priority_queue 是一个最大堆，但可以通过自定义比较器将其变为最小堆。通过指定比较函数，可以改变元素的排列顺序。

3.1 使用 greater 实现最小堆

可以使用 std::greater 来使得 priority_queue 变为最小堆，即优先级最低的元素会优先弹出。

#include <functional>  // 引入 less 和 greater

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

4. priority_queue 特性与注意事项

4.1 底层实现机制

priority_queue 的底层实现依赖于堆排序算法，因此其时间复杂度如下：

插入操作 push()：O(log n)
获取最大元素 top()：O(1)
删除最大元素 pop()：O(log n)

4.2 避免直接遍历

priority_queue 并不提供直接遍历所有元素的方法，原因是它的结构是基于堆的，内部顺序并不保证元素是按优先级依次排列的。因此，如果需要遍历所有元素，通常需要借助额外的容器或将元素逐个弹出。

4.3 谨慎修改元素

priority_queue 并不支持直接修改元素的优先级，一旦插入某个元素，想要调整优先级只能将该元素删除后，重新插入带有新优先级的元素。

5. 使用场景

priority_queue 适用于那些需要频繁取出优先级最高（或最低）元素的场景。常见的应用场景包括：

任务调度：根据任务的优先级决定执行顺序。
图算法：如Dijkstra算法和Prim算法，利用优先级队列高效处理最短路径或最小生成树。
数据流处理：实时处理数据流中前 k 大或前 k 小的元素。

实例如下：

以下是一个简单的例子，演示了如何使用 priority_queue 来处理最大堆和最小堆。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    // 默认最大堆
    priority_queue<int> maxHeap;

    maxHeap.push(3);
    maxHeap.push(5);
    maxHeap.push(1);

    cout << "Max-Heap: ";
    while (!maxHeap.empty())
    {
      cout << maxHeap.top() << " ";  // 输出 5 3 1
      maxHeap.pop();
    }
    cout << endl;

    // 最小堆
    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(3);
    minHeap.push(5);
    minHeap.push(1);

    cout << "Min-Heap: ";
    while (!minHeap.empty())
    {
        cout << minHeap.top() << " ";  // 输出 1 3 5
        minHeap.pop();
    }

    return 0;
}

在这里插入图片描述

7. 总结

priority_queue 是C++ STL中一个强大的容器适配器，用于处理需要频繁访问优先级最高（或最低）元素的场景。 通过了解其基本操作、自定义排序规则以及底层实现机制，开发者可以更加灵活地应用它来解决各类优先级相关的问题。不过，也要注意其一些限制，如无法直接遍历和修改元素优先级。

查看全文

http://www.kler.cn/news/311831.html