优先级队列 priority_queue 的使用及示例代码

admin管理员组

文章数量:1623798

一、简介

priority_queue 即 优先级队列（一种特殊的队列，其中的元素按照一定的优先级顺序排列，每次取出时都会取出具有最高优先级的元素，或者说可以获取队列中的最大/最小元素），它是C++标准模板库（Standard Template Library， STL）中的一个容器适配器，它基于堆（heap）的数据结构进行实现。优先级队列在很多算法和数据结构中都有广泛的应用，如：操作系统调度、图算法（如Dijkstra算法）、任务调度、模拟系统等方面。

对于一个包含n个元素的优先级队列（或者堆），其时间复杂度为：

获取队头（堆顶）元素，即 top() 操作 ： O(1)

删除堆顶元素，即 pop() 操作 ：               O(log n)

插入操作，即 push() 操作 ：                    O(log n)

要使用 priority_queue 需要包含以下头文件

#include <queue>

可参阅C++官方手册：

cplusplus/reference/queue/priority_queue/

 

 

二、优先级队列的定义

2.1 类模板定义

priority_queue的类模板定义如下：

template<
    // T是存储在队列中的元素类型
    class T, 

    // Container 是底层容器使用的类型，默认是vector
    // 也可以使用 deque
    class Container = std::vector<T>,
    
    // Compare 是一个可选参数
    // 它是一个用于定义元素之间的比较规则的函数对象。
    // 默认情况下，它使用less，使得优先级高的元素排在最前。
    // 也可以使用greater ，使得优先级低（最小值）排在最前。
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

2.2 最大值优先

定义一个优先获取最大元素的 整数优先级队列，可以使用如下几种方式：

priority_queue<int> pq;

priority_queue<int, vector<int>> pq;

priority_queue<int, vector<int>, less<int>> pq;

示例：

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

int main(){
    int nums[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    priority_queue<int> pq0(nums, nums + 10);
    
    priority_queue<int, vector<int>> pq1(nums, nums + 10);

    priority_queue<int, vector<int>, less<int>> pq2(nums, nums + 10);

    cout << "priority_queue 0: " << endl;
    while(pq0.size() > 0){
        cout << pq0.top() << " ";
        pq0.pop();
    }
    
    cout << "\npriority_queue 1: " << endl;
    while(pq1.size() > 0){
        cout << pq1.top() << " ";
        pq1.pop();
    }
    
    cout << "\npriority_queue 2: " << endl;
    while(pq2.size() > 0){
        cout << pq2.top() << " ";
        pq2.pop();
    }    
    cout << endl;
    
    return 0;
}

执行结果：

 2.3 最小值优先

定义一个优先获取最小元素的 整数优先级队列，可以使用如下几种方式：

priority_queue<int, vector<int>, greater<int>> pq;

示例代码：

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

int main(){
    int nums[10] = {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
    priority_queue<int, vector<int>, greater<int>> pq(nums, nums + 10);

    cout << "priority_queue : " << endl;
    while(pq.size() > 0){
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;

    return 0;
}

执行结果：

 

 

三、优先级队列的主要操作

priority_queue的主要操作如下：

push(x)： 将元素x插入优先级队列中。
pop()： 弹出优先级队列中的顶部元素。
top()： 获取优先级队列中的顶部元素。
size()： 返回优先级队列中的元素个数。
empty()： 判断优先级队列是否为空。

 

 

四、优先级队列的示例代码

4.1 string 优先级队列

string 优先级队列是根据字符串的字典序进行比较的。

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

int main(){
    string str[5] = {"abc", "def", "ghi", "jkl", "mno"};
    priority_queue<string> pq_less(str, str + 5);
    priority_queue<string, vector<string>, greater<string>> pq_greater(str, str + 5);

    pq_less.push("xyz");
    pq_greater.push("xyz");

    cout << "pq_less (最大值优先): " << endl;
    while(pq_less.size() > 0){
        cout << pq_less.top() << "  ";
        pq_less.pop();
    }

    cout << "\n\npq_greater(最小值优先): " << endl;
    while(!pq_greater.empty()){
        cout << pq_greater.top() << "  ";
        pq_greater.pop();
    }
    cout << endl;

    return 0;
}

输出结果：

4.2 pair<int, int> 优先级队列

pair<int, int> 优先级队列是根据第一个元素进行比较，如果第一个元素的值相同，则会根据第二个元素值的大小进行比较。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;

int main(){

    vector<PII> pii = {
        {1, 10}, 
        {1, 1000}, 
        {1, 100}, 
        {100, 20},
        {999, 0},
        {7, 7},
        {8, 2}        
    };

    priority_queue<PII> pq_less(pii.begin(), pii.end());
    priority_queue<PII, vector<PII>, greater<PII>> pq_greater(pii.begin(), pii.end());

    pq_less.push({666, 666});
    pq_greater.push({666, 666});

    cout << "pq_less (最大值优先): " << endl;
    while(pq_less.size() > 0){
        cout << pq_less.top().first << "\t" << pq_less.top().second << endl;
        pq_less.pop();
    }

    cout << "\n\npq_greater(最小值优先): " << endl;
    while(!pq_greater.empty()){
        cout << pq_greater.top().first << "\t" << pq_greater.top().second << endl;
        pq_greater.pop();
    }
    cout << endl;

    return 0;
}

执行结果：

 

如有不当或错误之处，恳请您的指正，谢谢！！！

本文标签： 优先级队列示例代码priorityqueue