0%

优先队列

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务,【不是普通队列的先进先出(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>

1
2
3
4
5
6
//升序队列,小顶堆
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) ,在此表示感谢。🍻🍻

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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的比较,先比较第一个元素,第一个相等比较第二个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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()};

}

输出

1
2
3
4
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)






觉得文章对您有帮助请我喝冰可乐吧 😉