priority_queue的使用

priority_queue的介紹

優先級佇列默認使用vector作為其底層存盤資料的容器，在vector上又使用了堆演算法將vector中的元素構造成堆的結構，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue，

注意： 默認情況下priority_queue是大堆，

priority_queue的定義方式

方式一： 使用vector作為底層容器，內部構造大堆結構，

priority_queue<int, vector<int>, less<int>> q1;

方式二： 使用vector作為底層容器，內部構造小堆結構，

priority_queue<int, vector<int>, greater<int>> q2;

方式三： 不指定底層容器和內部需要構造的堆結構，

priority_queue<int> q;

注意： 此時默認使用vector作為底層容器，內部默認構造大堆結構，

priority_queue各個介面的使用

priority_queue的各個成員函式及其功能如下：

示例：

#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int> q;
	q.push(3);
	q.push(6);
	q.push(0);
	q.push(2);
	q.push(9);
	q.push(8);
	q.push(1);
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl; //9 8 6 3 2 1 0
	return 0;
}

priority_queue的模擬實作

priority_queue的底層實際上就是堆結構，實作priority_queue之前，我們先認識兩個重要的堆演算法，（下面這兩種演算法我們均以大堆為例）

堆的向上調整演算法?

以大堆為例，堆的向上調整演算法就是在大堆的末尾插入一個資料后，經過一系列的調整，使其仍然是一個大堆，

調整的基本思想如下：
1、將目標結點與其父結點進行比較，
2、若目標結點的值比父結點的值大，則交換目標結點與其父結點的位置，并將原目標結點的父結點當作新的目標結點繼續進行向上調整；若目標結點的值比其父結點的值小，則停止向上調整，此時該樹已經是大堆了，

例如，現在我們在該大堆的末尾插入資料88，

我們先將88與其父結點54進行比較，發現88比其父結點大，則交換父子結點的資料，并繼續進行向上調整，

此時將88與其父結點87進行比較，發現88還是比其父結點大，則繼續交換父子結點的資料，并繼續進行向上調整，

這時再將88與其父結點89進行比較，發現88比其父結點小，則停止向上調整，此時該樹已經就是大堆了，

堆的向上調整演算法代碼：

//堆的向上調整（大堆）
void AdjustUp(vector<int>& v, int child)
{
	int parent = (child - 1) / 2; //通過child計算parent的下標
	while (child > 0)//調整到根結點的位置截止
	{
		if (v[parent] < v[child])//孩子結點的值大于父結點的值
		{
			//將父結點與孩子結點交換
			swap(v[child], v[parent]);
			//繼續向上進行調整
			child = parent;
			parent = (child - 1) / 2;
		}
		else//已成堆
		{
			break;
		}
	}
}

堆的向下調整演算法?

以大堆為例，使用堆的向下調整演算法有一個前提，就是待向下調整的結點的左子樹和右子樹必須都為大堆，

調整的基本思想如下：
1、將目標結點與其較大的子結點進行比較，
2、若目標結點的值比其較大的子結點的值小，則交換目標結點與其較大的子結點的位置，并將原目標結點的較大子結點當作新的目標結點繼續進行向下調整；若目標結點的值比其較大子結點的值大，則停止向下調整，此時該樹已經是大堆了，

例如，將該二叉樹從根結點開始進行向下調整，（此時根結點的左右子樹已經是大堆）

將60與其較大的子結點88進行比較，發現60比其較大的子結點小，則交換這兩個結點的資料，并繼續進行向下調整，

此時再將60與其較大的子結點87進行比較，發現60比其較大的子結點小，則再交換這兩個結點的資料，并繼續進行向下調整，

這時再將60與其較大的子結點54進行比較，發現60比其較大的子結點大，則停止向下調整，此時該樹已經就是大堆了，

堆的向下調整演算法代碼：

//堆的向下調整（大堆）
void AdjustDown(vector<int>& v, int n, int parent)
{
	//child記錄左右孩子中值較大的孩子的下標
	int child = 2 * parent + 1;//先默認其左孩子的值較大
	while (child < n)
	{
		if (child + 1 < n&&v[child] < v[child + 1])//右孩子存在并且右孩子比左孩子還大
		{
			child++;//較大的孩子改為右孩子
		}
		if (v[parent] < v[child])//左右孩子中較大孩子的值比父結點還大
		{
			//將父結點與較小的子結點交換
			swap(v[child], v[parent]);
			//繼續向下進行調整
			parent = child;
			child = 2 * parent + 1;
		}
		else//已成堆
		{
			break;
		}
	}
}

priority_queue的模擬實作

只要知道了堆的向上調整演算法和堆的向下調整演算法，priority_queue的模擬實作就沒什么困難了，

priority_queue的模擬實作代碼：

namespace cl //防止命名沖突
{
	//比較方式（使內部結構為大堆）
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
	//比較方式（使內部結構為小堆）
	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	//優先級佇列的模擬實作
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		//堆的向上調整
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2; //通過child計算parent的下標
			while (child > 0)//調整到根結點的位置截止
			{
				if (_comp(_con[parent], _con[child]))//通過所給比較方式確定是否需要交換結點位置
				{
					//將父結點與孩子結點交換
					swap(_con[child], _con[parent]);
					//繼續向上進行調整
					child = parent;
					parent = (child - 1) / 2;
				}
				else//已成堆
				{
					break;
				}
			}
		}
		//插入元素到隊尾（并排序）
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1); //將最后一個元素進行一次向上調整
		}
		//堆的向下調整
		void AdjustDown(int n, int parent)
		{
			int child = 2 * parent + 1;
			while (child < n)
			{
				if (child + 1 < n&&_comp(_con[child], _con[child + 1]))
				{
					child++;
				}
				if (_comp(_con[parent], _con[child]))//通過所給比較方式確定是否需要交換結點位置
				{
					//將父結點與孩子結點交換
					swap(_con[child], _con[parent]);
					//繼續向下進行調整
					parent = child;
					child = 2 * parent + 1;
				}
				else//已成堆
				{
					break;
				}
			}
		}
		//彈出隊頭元素（堆頂元素）
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(_con.size(), 0); //將第0個元素進行一次向下調整
		}
		//訪問隊頭元素（堆頂元素）
		T& top()
		{
			return _con[0];
		}
		const T& top() const
		{
			return _con[0];
		}
		//獲取佇列中有效元素個數
		size_t size() const
		{
			return _con.size();
		}
		//判斷佇列是否為空
		bool empty() const
		{
			return _con.empty();
		}
	private:
		Container _con; //底層容器
		Compare _comp; //比較方式
	};
}