STL的priorit_queue类

STL提供了priority_queue类，它是一个适配器容器。默认的基本容器类型是vector。priority_queue可以插入元素，但不能遍历元素。只能访问最上面的元素。元素在队列中出入时。会把优先级最高的元素放在队首，优先级最高的元素通过默认运算符<或比较函数对象来确定。priority_queue容器使用随机访问迭代器，采用支持front、push_back和pop_back 的容器，例如deque和vector。priority_queue最好实现为堆。下面是STL中priority_queue容器的一个简化规范：

template<class T ,class Container=vector<T>,
	class Compare=less<typename Container::value_type>>
class priority_queue
{
	public:
		explicit priority_queue(const Compare &=Compare(),
				const Container &=Container);
		//default constructor ;initializes an empty priority queue
		//A comparison function object may be supplied
		//precondition :none
		//postcondition :returns true if the priority queue is empty
		//otherwise returns false
		size_type size()const;
		//determines the size of the priority queue
		//the return type size_type is an integal type
		//precondition :none
		//postcondition:returns the nubmer of items that
		//are currently in the priority queue
		const value_type &top()const;
		//returns a reference to the highest priority element
		//in the priority queue
		//precondition :none
		//postcondition :the item remains at the top of the
		//priority queue

		void pop();
		//remove the highest priority element in the priority queue
		//precondition :none
		//postcondition :the priority queue has the highest
		//priority element at the top
		void push(const value_type &e);
		//Adds the item e to the priority queue .
		//precondition:none
		//postcondition :the priority queue has the highest
		//priority element at the top
};

STL还在<algorithm>中提供了堆算法。容器可以使用make_heap函数转换为堆，在使用sort_heap转换回容器。push_heap和pop_heap函数可以添加和删除堆的第一个元素，钙元素的优先级最高。堆算法要求使用随机访问迭代器。函数规范如下所示：

void push_heap(RandomIter first,RandomIter last);
void push_heap(RandomIter first,RandomIter last,Compare cmp);
//push an item onto the heap
//The value pushed is *(last-1)
//A comparison function object may be supplied.
void pop_heap(RandomIter first,RandomIter last);
void pop_heap(RandomITer first,RandomIter last,Compare cmp);
//pop an item onto the heap
//swaps first element with *(last-1) and  makes [first ,last-1] into a heap
//A compare function object may be supplied
void make_heap(RandomIter first,RandomIter second);
void make_heap(RandomIter first,RandomIter second,Compare cmp);
//Turns an existing container into a heap
//A compare function object may be supplied
void sort_heap(RandomIter first,RandomIter second);
void sort_heap(RandomIter first ,RandomIter second,Compare cmp);
//turns the heap back into original container
//A comparison function may be supplied

下面的程序演示了优先队列的用法和一个使用堆的操作的vector：

#include<algorithm>
#include<vector>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<queue>
using namespace  std;
int main()
{
	//declare a priority queue
	priority_queue<int,vector<int> > pq;
	//declare a vector
	vector<int> vheap;
	//declare a vector iterator
	vector<int>::iterator iter;
	//seed the random number generator
	srand(time(0));
	
	//fill the priority queue and vector with random numbers
	//push each nubmer of vector with random numbers
	//using the greater predicate;
	for(int i=0;i<25;i++)
	{
		int j=rand()%25;
		pq.push(j);
		vheap.push_back(j);
		push_heap(vheap.begin(),vheap.end(),greater<int>());
	}
	//show the generated numbers in their original order by
	//iterating through the vector
	cout<<"original numbers :"<<endl;
	for(iter=vheap.begin();iter!=vheap.end();iter++)
	{
		cout<<*iter<<" ";
	}
	//display the priority queue by popping the top off
	cout<<endl<<" Priority queue :"<<endl;
	while(!pq.empty())
	{
		cout<<pq.top()<<" ";
		pq.pop();
	}
	//display the vector as a heap by poping the top off
	cout<<endl<<" Heap :"<<endl;
	while(!vheap.empty())
	{
		cout<<vheap[0]<<" ";
		pop_heap(vheap.begin(),vheap.end(),greater<int>());
		vheap.pop_back();
	}
	cout<<endl;
	return 0;
}