C++深入刨析優(yōu)先級隊列priority_queue的使用

更新時間：2022年08月03日 10:57:28 作者：Rookiep

最近我學(xué)習(xí)了C++中的STL庫中的優(yōu)先級隊列（priority_queue）容器適配器，對于優(yōu)先級隊列，我們不僅要會使用常用的函數(shù)接口，我們還有明白這些接口在其底層是如何實現(xiàn)的

一、priority_queue的介紹

priority_queue官方文檔介紹

翻譯：

優(yōu)先隊列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個元素總是它所包含的元素中最大的。
此上下文類似于堆，在堆中可以隨時插入元素，并且只能檢索最大堆元素(優(yōu)先隊列中位于頂部的元素)。
優(yōu)先隊列被實現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為優(yōu)先級隊列的底層容器類，priority_queue提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的“尾部"彈出，其稱為優(yōu)先隊列的頂部。
底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計的容器類。容器應(yīng)該可以通過隨機訪問迭代器訪問，并支持以下操作:

empty()：檢測容器是否為空。

size()：返回容器中有效元素個數(shù)。

front()：返回容器中第一個元素的引用。

push_back()：在容器尾部插入元素。

pop_back()：刪除容器尾部元素。

標(biāo)準(zhǔn)容器類vector和deque滿足這些需求。默認(rèn)情況下，如果沒有為特定的priority_queue類實例化指定容器類，則使用vector。
需要支持隨機訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時自動調(diào)用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。

二、priority_queue的使用

優(yōu)先級隊列默認(rèn)使用vector作為其底層存儲數(shù)據(jù)的容器，在vector上又使用了堆算法（堆的創(chuàng)建與應(yīng)用）將vector中元素構(gòu)造成堆的結(jié)構(gòu)，因此priority_queue就是堆，所有需要用到堆的位置，都可以考慮使用priority_queue。注意:默認(rèn)情況下priority_queue是大堆。

??????：常用的函數(shù)接口

priority_queue()/priority_queue(first,last),構(gòu)造優(yōu)先級隊列。
empty()，檢測優(yōu)先級隊列是否為空，若是返回True。
top()，返回優(yōu)先級隊列中最大（最?。┰兀炊秧斣?。
push()，在優(yōu)先級隊列中插入元素。
pop()，刪除優(yōu)先級隊列中最大（最?。┰?，即堆頂元素。

下面我們就舉一個例子:

存放自定義類型，這樣更具代表性！

template<class T>
class greater
{
public:
	bool operator()(const T& p1, const T& p2) const
	{
		return p1 > p2;
	}
};
struct person
{
	person(string name = "", int age = -1)
		:_name(name)
		, _age(age)
	{}
	bool operator<(const person& p) const
	{
		return _age < p._age;
	}
	bool operator>(const person& p) const
	{
		return _age > p._age;
	}
	string _name;
	int _age;
};
ostream& operator<<(ostream& out, const person& p)
{
	out << "name:" << p._name << "   " << "age:" << p._age << endl;
	return out;
}
void test02()
{
	person arr[] = { { "pxl", 23 },
					 { "dyx", 21 }, 
					 { "wjz", 24 }, 
					 { "ztd", 20 } };
	priority_queue<person, vector<person>, greater<person>> pq(arr, arr + sizeof(arr) / sizeof(arr[0]));//小堆
	pq.push(person("yzc", 22));
	cout <<"堆頂元素是："<< pq.top() << endl;
	while (!pq.empty())
	{
		cout << pq.top() << endl;
		pq.pop();
	}
}
int main()
{
	test02();//自定義類型
	system("pause");
	return 0;
}

??????注意點：

如果存放自定義類型，我們想要自定義類型像內(nèi)置類型一樣進行各種運算，那么就要在類中重載相應(yīng)的運算符。
輸出自定義類型，需要重載流輸出。
在priority_queue的第三個參數(shù)時，我們可以用庫中的greater函數(shù)（頭文件：functional），也可以我們自己寫一個仿函數(shù)（如上述代碼）。

三、priority_queue的模擬實現(xiàn)

	template<class T>
	struct less
	{
		bool operator()(const T& x, const T&  y) const
		{
			return x < y;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T&  y) const
		{
			return x > y;
		}
	};
	// 優(yōu)先級隊列 -- 大堆 < 小堆 >
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		void AdjustUp(int child)
		{
			Compare comFunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);
		}
		void AdjustDown(int parent)
		{
			Compare comFunc;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				//if (child+1 < _con.size() && _con[child] < _con[child+1])
				if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
				{
					++child;
				}
				//if (_con[parent] < _con[child])
				if (comFunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void pop()
		{
			assert(!_con.empty());
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown(0);
		}
		const T& top()
		{
			return _con[0];
		}
		size_t size()
		{
			return _con.size();
		}
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
	};

代碼解釋：

這里模擬實現(xiàn)底層容器缺省參數(shù)使用vector，比較規(guī)則使用Less。
這里的比較方式均是自己實現(xiàn)的仿函數(shù)。

四、容器適配器

4.1、什么是適配器

適配器是一種設(shè)計模式（設(shè)計模式是一套被反復(fù)使用的，多數(shù)人知曉的，經(jīng)過分類編目的，代碼設(shè)計經(jīng)驗的總結(jié)），該模式是講一個類的接口轉(zhuǎn)換成客戶希望的另一個接口。

4.2、適配模式

在計算機編程中，適配器模式（有時候也稱包裝樣式或者包裝）將一個類的接口適配成用戶所期待的。一個適配允許通常因為接口不兼容而不能在一起工作的類工作在一起，做法是將類自己的接口包裹在一個已存在的類中。
適配器模式主要應(yīng)用于，當(dāng)接口里定義的方法無法滿足客戶的需求，或者說接口里定義的方法的名稱或者方法界面與客戶需求有沖突的情況。
兩類模式：對象適配器模式 - 在這種適配器模式中，適配器容納一個它我包裹的類的實例。在這種情況下，適配器調(diào)用被包裹對象的物理實體。類適配器模式 - 這種適配器模式下，適配器繼承自已實現(xiàn)的類（一般多重繼承）。
在計算機編程中，適配器包括：容器適配器、迭代器適配器、泛函適配器等。