优先队列

发表于 2021-04-08 更新于 2022-11-15 分类于技术阅读次数：本文字数： 5.7k 阅读时长 ≈ 5 分钟

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级，优先级最高的元素最先得到服务；优先级相同的元素按照其在优先队列中的顺序得到服务，【不是普通队列的先进先出(FIFO)】。优先队列往往用**堆**来实现。🌴

🍽操作

优先队列至少需要支持下述操作：

插入带优先级的元素（insert_with_priority）
取出具有最高优先级的元素（pull_highest_priority_element）
查看最高优先级的元素（peek）：O(1) 时间复杂度

其它可选的操作：

检查优先级高的一批元素
清空优先队列
批插入一批元素
合并多个优先队列
调整一个元素的优先级

🍿实现

初级实现

有许多简单低效的实现。如用一个有序的数组；或使用无序数组，在每次取出时搜索全集合，这种方法插入的效率为O(1)，但取出时效率为O(n)。

典型实现

出于性能考虑，优先队列用堆来实现，具有O(log n)时间复杂度的插入元素性能，O(n)的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为O(log n)，构造二叉树的时间复杂度为O(n log n)。

从计算复杂度的角度，优先级队列等价于排序算法。

有一些特殊的堆为优先队列的实现提供了额外的性能：二叉堆的插入与提取操作的时间复杂度为O(log n)，并可以常量时间复杂度的peek操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度，[1]，但删除操作的时间复杂度为O(log n)。Brodal queue（英语：Brodal queue）具有最糟糕情况下的常量复杂度但算法相当复杂因而不具有实用性。

对于整型、浮点型等具有有限值域的元素的数据类型，优先队列有更快的实现。

库实现

优先队列是计算机科学中的一类”容器数据类型”。

标准模板库（STL）以及1998年的C++标准确定优先队列是标准模板库的容器适配器模板。其实现了一个需要三个参数的最大优先队列：比较函数（缺省情况是小于函数less）、存储数据所用的容器类型（缺省情况是向量vector）以及指向序列开始和结束位置的两个迭代器。和标准模板库中其他的真实容器不同，优先队列不允许使用其元素类型的迭代器，而必须使用优先队列抽象数据类型的迭代器。标准模板库还实现了支持随机访问数据容器的优先队列–二叉最大堆。Boost C++库也在其中实现了堆结构。

🌸STL priority_queue 优先级队列用法

优先级队列是一个容器适配器，它提供对最大（默认）元素的恒定时间查找，但以对数插入和提取为代价。可以提供用户提供的比较来更改顺序，例如使用std :: greater 会使最小的元素显示为top（）。使用priority_queue类似于在某些随机访问容器中管理堆，其好处是不会意外使堆无效。

🌻priority_queue 操作

对 priority_queue 进行操作有一些限制：

push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。
push(T&& obj)：将obj放到容器的适当位置，这通常会包含一个排序操作。
emplace(T constructor a rgs…)：通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
top()：返回优先级队列中第一个元素的引用。
pop()：移除第一个元素。
size()：返回队列中元素的个数。
empty()：如果队列为空的话，返回true。
swap(priority_queue& other)：和参数的元素进行交换，所包含对象的类型必须相同。

语法

1 2	template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>> class priority_queue

Type
要存储在 priority_queue 中的元素数据类型。

*Container 容器
用来实现 priority_queue 的基础容器的类型，比如vector,deque等，默认是vector .

Functional
一种提供函数对象的类型，该函数对象将两个元素值作为排序键进行比较，以确定其在 priority_queue 中的相对顺序。此参数为可选自变量，默认值是二元谓词 less<typename Container::value_type>。

//升序队列，小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//降序队列，大顶堆
priority_queue <int,vector<int>,less<int> >q;

//greater和less是std实现的两个仿函数（就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()，这个类就有了类似函数的行为，就是一个仿函数类了）

基本类型优先队列的例子：

示例来自 c++优先队列(priority_queue)用法详解 - 华山青竹 - 博客园 (cnblogs.com) ，在此表示感谢。🍻🍻

#include<iostream>
#include <queue>
using namespace std;
int main()
{
    //对于基础类型 默认是大顶堆
    priority_queue<int> a;
    //等同于 priority_queue<int, vector<int>, less<int> > a;

    //      这里一定要有空格，不然成了右移运算符↓↓
    priority_queue<int, vector<int>, greater<int> > c;  //这样就是小顶堆
    priority_queue<string> b;

    for (int i = 0; i < 5; i++)
    {
        a.push(i);
        c.push(i);
    }
    while (!a.empty())
    {
        cout << a.top() << ' ';
        a.pop();
    }
    cout << endl;

    while (!c.empty())
    {
        cout << c.top() << ' ';
        c.pop();
    }
    cout << endl;

    b.push("abc");
    b.push("abcd");
    b.push("cbd");
    while (!b.empty())
    {
        cout << b.top() << ' ';
        b.pop();
    }
    cout << endl;
    return 0;
}

运行结果：

1
2
3

4 3 2 1 0
0 1 2 3 4
cbd abcd abc

用pair做优先队列元素的例子：

规则：pair的比较，先比较第一个元素，第一个相等比较第二个。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    priority_queue<pair<int, int> > a;
    pair<int, int> b(1, 2);
    pair<int, int> c(1, 3);
    pair<int, int> d(2, 5);
    a.push(d);
    a.push(c);
    a.push(b);
    while (!a.empty())
    {
        cout << a.top().first << ' ' << a.top().second << '\n';
        a.pop();
    }
}

运行结果：

1
2
3

2 5
1 3
1 2

用自定义类型做优先队列元素的例子

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

//方法1
struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};

//方法2
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b)
    {
        return a.x < b.x; //大顶堆
    }
};

int main()
{
    tmp1 a(1);
    tmp1 b(2);
    tmp1 c(3);
    priority_queue<tmp1> d;
    d.push(b);
    d.push(c);
    d.push(a);
    while (!d.empty())
    {
        cout << d.top().x << '\n';
        d.pop();
    }
    cout << endl;

    priority_queue<tmp1, vector<tmp1>, tmp2> f;
    f.push(b);
    f.push(c);
    f.push(a);
    while (!f.empty())
    {
        cout << f.top().x << '\n';
        f.pop();
    }
}

示例，来自 https://en.cppreference.com/w/cpp/container/priority_queue

#include<bits/stdc++.h>
using namespace std;


#include <functional>
#include <queue>
#include <vector>
#include <iostream>

template<typename T>
void print_queue(T q) { // NB: pass by value so the print uses a copy
    while(!q.empty()) {
        std::cout << q.top() << ' ';
        q.pop();
    }
    std::cout << '\n';
}

int main() {

    //默认大顶堆  队头元素最大
    std::priority_queue<int> q;

    const auto data = {1,8,5,6,3,4,0,9,7,2};

    for(int n : data)
        q.push(n);

    print_queue(q);

    // 优先输出小的元素
    std::priority_queue<int, std::vector<int>, std::greater<int>>
            q2(data.begin(), data.end());
    print_queue(q2);

    priority_queue<int,vector<int>,greater<int> >q22;
    for(int n:data)
        q22.push(n);
    print_queue(q22);

    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);

    for(int n : data)
        q3.push(n);

    print_queue(q3);


    auto cmp2=[](int left, int right){return()};

}

输出

9 8 7 6 5 4 3 2 1 0 
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
8 9 6 7 4 5 2 3 0 1

补充

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode） (leetcode-cn.com) 这一题可使用优先队列的大顶推

🍉应用

优先队列常用于操作系统的任务调度，也是贪心算法的重要组成部分。

🌳参考文献

优先队列 - Wikiwand

std::priority_queue - cppreference.com

priority_queue 类 | Microsoft Docs

c++优先队列(priority_queue)用法详解 - 华山青竹 - 博客园 (cnblogs.com)

🍽操作

🍿实现

初级实现

典型实现

库实现

🌸STL priority_queue 优先级队列 用法

🌻priority_queue 操作

🍉应用

🌳参考文献

🌸STL priority_queue 优先级队列用法