一、什么是priority_queue?

priority_queue是C++標(biāo)準(zhǔn)庫中的一個(gè)容器適配器，用于實(shí)現(xiàn)優(yōu)先隊(duì)列（priority queue）的數(shù)據(jù)結(jié)構(gòu)。優(yōu)先隊(duì)列是一種特殊的隊(duì)列，其中的元素按照一定的優(yōu)先級(jí)進(jìn)行排序，每次取出的元素都是優(yōu)先級(jí)最高的。它的優(yōu)先級(jí)是可以通過傳入?yún)?shù)自己調(diào)整的，它的底層實(shí)現(xiàn)通常使用堆(heap)數(shù)據(jù)結(jié)構(gòu)。以下是堆結(jié)構(gòu)的學(xué)習(xí)鏈接：堆(建堆算法，堆排序)

主要特點(diǎn)

• 元素有序：隊(duì)列中的元素會(huì)根據(jù)其優(yōu)先級(jí)進(jìn)行排序，優(yōu)先級(jí)最高的元素總是位于隊(duì)列的頭部（或稱為隊(duì)首）。
• 操作：主要操作包括插入新元素（push）、刪除優(yōu)先級(jí)最高的元素（pop）以及訪問優(yōu)先級(jí)最高的元素（top，但不刪除）。
• 默認(rèn)行為：默認(rèn)情況下，priority_queue使用最大堆實(shí)現(xiàn)，即優(yōu)先級(jí)最高的元素（值最大的元素）存儲(chǔ)在根節(jié)點(diǎn)。但可以通過指定比較函數(shù)來改變?cè)氐呐判蚍绞?，例如使用std::greater可以實(shí)現(xiàn)最小堆，即優(yōu)先級(jí)最低的元素（值最小的元素）存儲(chǔ)在根節(jié)點(diǎn)。

二、priority_queue如何用？

模板參數(shù)

priority_queue的模板定義通常包含三個(gè)參數(shù)：

• typename T：元素類型。
• typename Container = std::vector<T>：底層容器類型，默認(rèn)為std::vector<T>。雖然std::deque也滿足條件，但std::vector因其高效的隨機(jī)訪問性能而更常被用作底層容器。
• typename Compare = std::less<T>：比較函數(shù)類型，用于確定元素的優(yōu)先級(jí)。默認(rèn)為std::less<T>，表示元素按從大到小的順序排列；若需按從小到大的順序排列，可指定為std::greater<T>。

以上是priority_queue的接口函數(shù)，該篇文章只來學(xué)習(xí)和模擬c++11以前的接口。

以下是這些接口的使用：

//使用示例
#include<iostream>
#include<queue>
using namespace std;
//這是自定義優(yōu)先級(jí)的一種格式
template<typename T>
class gt
{
public:
	//如果返回true則b優(yōu)先，返回false則a優(yōu)先，所以這里使用gt會(huì)生成小堆
	bool operator()(T a, T b)
	{
		return a > b;
	}
private:
};
int main()
{
	priority_queue<int> heap1;//int表示儲(chǔ)存的類型
	priority_queue<int, vector<int>> heap2;//這里vector表示使用的底層容器，這里也可以換成deque<int>。
	
	//greater為編譯器提供的類模板，默認(rèn)的優(yōu)先級(jí)是大堆，而使用它可以生成小堆。
	priority_queue<int, vector<int>, greater<int>> heap3;

	//當(dāng)然也可以自己設(shè)計(jì)一個(gè)優(yōu)先級(jí)方式傳入，該方法常常用于儲(chǔ)存自定義類型，而內(nèi)置類型編譯器提供的就夠用。
	priority_queue<int, vector<int>, gt<int>> heap4;

	//push接口用于存入元素
	heap4.push(2);
	heap4.push(7);
	heap4.push(1);
	heap4.push(5);
	cout << heap4.size() << endl;//size用于計(jì)算隊(duì)列中元素的個(gè)數(shù)
	while (!heap4.empty())//empty用于判斷隊(duì)列是否為空
	{
		cout << heap4.top() << ' ';//top獲取隊(duì)頭元素
		heap4.pop();//pop刪除隊(duì)頭元素
	}
	return 0;
}

以上輸出為：

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

1.模板參數(shù)

首先為了區(qū)別于庫里面的優(yōu)先級(jí)隊(duì)列，我們可以用命名空間限制它的作用域。通過觀察庫里面的priority_queue模板參數(shù)一共有三個(gè)，第一個(gè)為儲(chǔ)存的元素類型，第二個(gè)參數(shù)為需要用的底層容器（默認(rèn)為vector），第三個(gè)參數(shù)為用來調(diào)整優(yōu)先級(jí)的類模板（需要我們寫一個(gè)默認(rèn)模板），那么我們可以做以下設(shè)計(jì)：

#include<iostream>
#include<vector>
using namespace std;
namespace byte//用命名空間限制它的作用域，來區(qū)別于庫里面的優(yōu)先級(jí)隊(duì)列
{
	template<typename T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		//...
	private:
		//...
	};
}

 注意：這里vector模板我們可以使用庫里面的，但優(yōu)先級(jí)隊(duì)列模板（less<T>）需要我們自己寫。

2.成員變量

STL的任何模擬，如果在考慮成員變量如何設(shè)計(jì)而發(fā)愁，我們可以去想如何儲(chǔ)存對(duì)象的數(shù)據(jù)進(jìn)而來設(shè)計(jì)我們的成員變量。這里我們用的是容器Container（即vector<int>）來儲(chǔ)存數(shù)據(jù)的，所以我們的成員變量之一類型一定是Container，其次因?yàn)橄氲讲煌瑢?duì)象傳入的Compare可能不同，具有特殊性，所以我們也可以把Compare（優(yōu)先級(jí)調(diào)整的類模板）作為成員變量。如下：

private:
	Container arr;
	Compare comp;

3.成員函數(shù)

因?yàn)樵趐riority_queue模擬中并不涉及到動(dòng)態(tài)內(nèi)存開辟和一些特殊理，所以這里的構(gòu)造函數(shù)用編譯器默認(rèn)提供的構(gòu)造函數(shù)就夠用了，并不需要我們自己編寫。

在優(yōu)先級(jí)隊(duì)列中因?yàn)樯婕暗蕉训恼{(diào)整所以在push和pop接口的設(shè)計(jì)中有些復(fù)雜，其他接口的設(shè)計(jì)都非常簡(jiǎn)單就不在講解，后面大家直接看源碼。

3.1.push

首先需要把a(bǔ)rr看做是一個(gè)堆結(jié)構(gòu)，無論arr里面有沒有元素，然后直接把元素push_back到arr中，此時(shí)該元素所在位置為堆底，而且并不一定是正確的位置，接下來要做的就是對(duì)該元素進(jìn)行向上調(diào)整。

父子節(jié)點(diǎn)的定義：子節(jié)點(diǎn)記為child，父節(jié)點(diǎn)記為father。

child=arr.size()-1

father=(child-1)/2（理解原理后可以當(dāng)做公式記憶，可通過一下鏈接參考學(xué)習(xí)）

向下調(diào)整的方法我在以下文章中有具體講解：

堆(建堆算法，堆排序)_初始建堆算法

3.2.pop

該函數(shù)主要功能是pop堆頂元素，但是如果直接pop堆頂元素（下標(biāo)為0）的話，那么下標(biāo)為1的會(huì)成為堆頂元素，會(huì)使原來的父子關(guān)系和兄弟關(guān)系混亂，要重新調(diào)整起來極其復(fù)雜，所一需要換一種方案，我們可以把堆頂元素與堆底元素交換然后pop堆底元素，然后對(duì)堆進(jìn)行向下調(diào)整。

父子節(jié)點(diǎn)的定義：子節(jié)點(diǎn)記為child，父節(jié)點(diǎn)記為father。

father=0

child=father*2+1（這里father和child的計(jì)算公式是可以互推的）

向下調(diào)整的方法我在以下文章中有具體講解：

堆(建堆算法，堆排序)_初始建堆算法

四、源碼

#include<iostream>
#include<vector>
using namespace std;
namespace byte
{
	template<typename T>
	class less
	{
	public:
		//如果返回true則b優(yōu)先，返回false則a優(yōu)先，所以這里使用gt會(huì)生成小堆
		bool operator()(T a, T b)
		{
			return a < b;
		}
	private:
	};
	template<typename T>
	class greater
	{
	public:
		//如果返回true則b優(yōu)先，返回false則a優(yōu)先，所以這里使用gt會(huì)生成小堆
		bool operator()(T a, T b)
		{
			return a > b;
		}
	private:
	};

	template<typename T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:

		void AdjustUP()
		{
			int child = arr.size() - 1, father = (child - 1) / 2;
			while (child > 0)
			{
				if (comp(arr[father], arr[child]))
				{
					std::swap(arr[child], arr[father]);
					child = father;
					father = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDOWN()
		{
			int father = 0, child = father * 2 + 1;
			while (child < arr.size())
			{
				if (child + 1 < arr.size() && comp(arr[child], arr[child + 1]))
				{
					child++;
				}
				if (comp(arr[father], arr[child]))
				{
					std::swap(arr[child], arr[father]);
					father = child;
					child = father * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
		void push(T x)
		{
			arr.push_back(x);
			AdjustUP();
		}
		void pop()
		{
			std::swap(arr[0], arr[arr.size() - 1]);
			arr.pop_back();
			AdjustDOWN();
		}
		T top()
		{
			return arr[0];
		}
		size_t size()
		{
			return arr.size();
		}
		bool empty()
		{
			return arr.size() == 0;
		}
	private:
		Container arr;
		Compare comp;
	};
}

到此這篇關(guān)于c++中priority_queue模擬的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)c++ priority_queue模擬內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！ 

最新評(píng)論