C++ priority_queue 優先隊列

C++中優先隊列的實現是利用堆來實現的。在STL庫中的make_heap ， pop_heap以及push_heap來實現的。

主要的操作有：

1 push ： push進一個元素，並調整堆

2 pop : 彈出對首元素，並調整堆

3 size ： 返回隊列中的元素個數

4 empty ： 隊列是否為空

5 top ： 取出隊首元素，但不刪除該元素

#include 
#include 
#include 
#include 
using namespace std;

template, 
	class Compare = less > 
	//采用類模板的形式，定義數組的元素類型以及底層實現的容器類型（此處為vector）
	//以及用於比較的函數對象 less。關於less greater，參見。。。
	
class my_priority_queue
{
private:
	Sequence c;    //用於存放元素的vector
	Compare comp;  //用於比較的函數對象
	
public: 
	//類模板內部定義的類型
	typedef typename Sequence::value_type value_type;
	typedef typename Sequence::size_type size_type;
	typedef typename Sequence::reference  reference;
	typedef typename Sequence::const_reference  const_reference;


	my_priority_queue():c(){}

	//如果沒有指定比較函數，那麼使用less
	template
	my_priority_queue(InputIterator beg, InputIterator end, const Compare &x = Compare()):
		c(beg, end),comp(x)
	{
		make_heap(c.begin(),c.end(), comp);
	}

	bool empty() const
	{
		return c.empty();
	}

	size_type size() const
	{
		return c.size();
	}

	const_reference top() const
	{
		return c.front();
	}

	void pop()
	{
		if(empty())
		{
			cout << "pop empty" << endl;
			exit(1);
		}
		pop_heap(c.begin(), c.end(), comp);
		c.pop_back();
	}

	void push(const value_type &x)
	{
		c.push_back(x);
		push_heap(c.begin(), c.end(), comp);
	}
};


int main()
{
	my_priority_queue mpq;
	int A[] = {4,2,3,1};
	my_priority_queue > mpq2(A, A+4);
	mpq2.push(5);

	cout << "mpq2.size() = " << mpq2.size() << endl;

	while(!mpq2.empty())
	{
		cout << mpq2.top() << " ";
		mpq2.pop();
	}
	if (mpq2.empty())
	{ 
		cout << "mpq2 is empty..." << endl;
	}
	//使用greater比較函數， greater作為一個類型實例化類模板實參；greater() 作為函數對象！

	my_priority_queue, greater > mpq3(A, A+4, greater());
	mpq3.push(5);

	cout << "mpq3.size() = " << mpq3.size() << endl;

	while(!mpq3.empty())
	{
		cout << mpq3.top() << " ";
		mpq3.pop();
	}
	if(mpq3.empty())
	{
		cout << "Empty.." << endl;
	}
	return 0;
}