优先级队列

发表于   |  

优先队列

参考了《挑战程序设计竞赛》 第二版 P71 2.4.2 优先队列和堆的部分

概念

　　能高效地完成下列操作的数据结构叫优先队列

  • 插入一个值
  • 取出最小值（获得数值，并删除）

　　能够利用二叉树满足上述问题，通常也叫堆，堆是一颗二叉树，满足子节点的值不小于父节点的值。在堆中插入一个数值，可以简单的证明，上述两种操作的时间复杂度都是跟树的高度成正比，简略证明如下

  • 插入一个值：将插入的值放在堆的最后节点上，该节点不断的与父节点调整（如果需要的话），直至树根
  • 取出最小值：最小值即为树根，取出以后，将堆的最后一个节点放在树根，此时有可能不是堆了，因此从树根元素开始不断交换（如果需要的话），直至最底层

C++ STL实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <queue>
#include <cstdio>
using namespace std;
int main() {
	// 声明
	priority_queue<int> pque;
	// 插入元素
	pque.push(1);
 	// 循环
	while (!pque.empty()) {
		// 取值，删除
		printf("%d\n", pque.top());
		pque.pop();
	}
	return 0;
}