priority_queue使用

Created: March 19, 2024 12:13 PM

在C++中，**priority_queue是标准模板库（STL）中的一种容器适配器，它提供了一种方式来维护一个集合，使得其中的元素总是按照某种给定的顺序（通常是根据元素的值排序）排列。priority_queue**支持基本操作，如插入新元素和从队列中取出并移除顺序最高（或最低）的元素。

**priority_queue的实现通常是一个最大堆，这意味着队列的顶部（可以通过top()**方法访问）总是当前队列中最大的元素。如果需要最小堆行为，则可以通过提供自定义比较函数来实现。

基本用法

要使用**priority_queue，你需要包含头文件<queue>**。

cppCopy code
#include <iostream>#include <queue>int main() {
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(30);
    pq.push(10);
    pq.push(20);

    // 获取并移除顶部元素（最大的元素）
    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 访问顶部元素
        pq.pop(); // 移除顶部元素
    }
    // 输出: 30 20 10
}

自定义比较函数

你可以自定义**priority_queue**的排序行为，通过提供自定义的比较函数类型。这在需要最小堆或根据特定标准排序队列时特别有用。

cppCopy code
#include <iostream>#include <queue>#include <vector>#include <functional> // std::greaterint main() {
    // 创建一个最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    // 插入元素
    pq.push(30);
    pq.push(10);
    pq.push(20);

    // 获取并移除顶部元素（最小的元素）
    while (!pq.empty()) {
        std::cout << pq.top() << " "; // 访问顶部元素
        pq.pop(); // 移除顶部元素
    }
    // 输出: 10 20 30
}

关键点

• priority_queue提供了有限的接口，主要包括push()、pop()、top()、**empty()和size()**方法。
• 它不提供遍历容器的方式，因为**priority_queue**的目的是保持顶部元素总是最大（或根据提供的比较函数确定的顺序）的元素，而不是提供对所有元素的随机访问。
• 默认情况下，**priority_queue**是最大堆，但通过提供自定义的比较函数，可以改变其行为（如示例中的最小堆）。

**priority_queue**在需要快速访问集合中的最大（或最小）元素的场景中非常有用，比如任务调度、事件驱动的模拟、路径查找算法中的开放集管理等。