priority queue

C++的优先队列使用

优先队列特点

优先队列维护在队列头部维持一个最值，使用堆结构进行维护
因此插入的时间复杂度为log(n)，n为此时树中的元素个数，取出最值的时间复杂度为O(1)
默认为维持最大值，大根堆

#include <queue>
priority_queue<int> heap ;

比较函数

维持最小值

#include <queue>
struct cmp{
	bool operator()(int a, int b)
	{
		return a > b ;
	}	
};

int main()
{
	priority_queue<int, vector<int>, cmp> heap ;
	heap.push(1) ; //插入元素
	heap.top() ; //取出最值
	heap.pop() ; //删除最值
}

原型

priority_queue<Type, Container, Functional>

Type： 基本元素的数据类型类型
Container：保存数据的容器，必须是数组实现的容器，比如vector，deque，默认用的是vector
Functional：比较方法

参考

http://www.cnblogs.com/flyoung2008/articles/2136485.html