priority_queue 的使用(C++)

priority_queue 的使用(C++)

能够完成下列操作的数据结构叫作:priority_queue ,即优先队列。

  • 插入一个数值
  • 去除最小(大)的数值(获得数值,并且删除)

为了每种操作都可以在 \(O(logn)\) 的时间内完成,使用堆的结构来完成。

(本文只介绍程序设计竞赛中 priority_queue 的使用,不详细介绍其实现的方法,以及堆的性质。)

C++ 中,STL 里的 priority_queue 就实现了优先队列。在 C++ 中,priority_queue 中取出数值得到的是最大值。

一个简单的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <queue>
#include <cstdio>

using namespace std;

int main() {
priority_queue<int> pque;
pque.push(3);
pque.push(5);
pque.push(1);

while (!pque.empty()) {
printf("%d\n", pque.top()); // 获取最大值并删除
pque.pop();
}

return 0;
}

其实这里就是提供了从序列中,不断取出最大值的一种方法,其时间复杂度在 \(O(logn)\) 内。

那么如果要取出最小值呢?看 priority_queue 的构造函数。

1
2
3
4
5
template<
class T, // 数据类型
class Container = std::vector<T>, // 容器模板
class Compare = std::less<typename Container::value_type> // 排序方法
> class priority_queue;

我们先考虑第三个参数,Compare,这是一个结构体。可以看出默认使用 std::less,那么我们改为 std::greater,就可以进行 大 -> 小的替换,即:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <queue>
#include <cstdio>

using namespace std;

int main() {
priority_queue<int, vector<int>, greater<int> > pque;
pque.push(3);
pque.push(5);
pque.push(1);

while (!pque.empty()) {
printf("%d\n", pque.top()); // 获取最小值并删除
pque.pop();
}

return 0;
}

因为如果使用第三个参数,第二个参数就不能为空或默认值,所以这里使用了第二个参数,其本质上是 priority_queue 的承载容器,就类似于排序是在这个容器上进行的。

在这里已经完成了对 int 类型的优先队列构造,但是在实际运用中,我们还会用到其他数据类型,比如 stringpair<T, T>,亦或者是自己构造的结构体。

如果是常用的 STL 类型,其实现都和上文中的 int 类似,使用 pair<int, int> ,要注意默认按照第一个参数的大小来排序。如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;

int main() {
priority_queue<pii, vector<pii>, greater<pii> > pque;
// priority_queue<pii> pque;

pque.push(make_pair(1, 5));
pque.push(make_pair(5, 2));
pque.push(make_pair(3, 1));

while (!pque.empty()) {
printf("%d\t%d\n", pque.top().first, pque.top().second);
pque.pop();
}

return 0;
}

如果自定义结构体,那么就要定义结构体的比较方法,比如:

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
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node {
int x, y;

Node() {}; // 构造函数
Node(int x, int y) : x(x), y(y) {} // 初始化
};

bool operator<(Node a, Node b) { // 返回 true,a 的优先级低于 b
// x 大的优先级低,x 小的排在队前
// x 相等时,y 大的优先级低,y 小的排在队前
if (a.x == b.x) return a.y > b.y;
return a.x > b.x;
}

int main() {
priority_queue<Node> pque; // greater 没有定义, < 是 less
for (int i = 0; i < 10; ++i)
pque.push(Node(rand(), rand()));

while (!pque.empty()) {
printf("%d\t%d\n", pque.top().x, pque.top().y);
pque.pop();
}

return 0;
}

如果要使用 greater 则,更改为:

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
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

struct Node {
int x, y;

Node() {}; // 构造函数
Node(int x, int y) : x(x), y(y) {} // 初始化
};
bool operator>(Node a, Node b) { // 返回 true,a 的优先级大于 b
// x 大的优先级高,排在队前
// x 相等时,y 大的优先级高,排在队前
if (a.x == b.x) return a.y > b.y;
return a.x > b.x;
}

int main() {
priority_queue<Node, vector<Node>, greater<Node> > pque;
for (int i = 0; i < 10; ++i)
pque.push(Node(rand(), rand()));

while (!pque.empty()) {
printf("%d\t%d\n", pque.top().x, pque.top().y);
pque.pop();
}

return 0;
}

如果要重写仿函数,即重写 Compare,比如:

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
#include <iostream>
#include <queue>
#include <string>

using namespace std;

struct cmp {
bool operator() (string a, string b) {
return a.length() > b.length();
}
};

int main() {
priority_queue<string, vector<string>, cmp> pque;

pque.push("gkalkja");
pque.push("as");
pque.push("asfkafhlakghfladj");

while (!pque.empty()) {
cout << pque.top() << endl;
pque.pop();
}
return 0;
}
# C++

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×