一、priority_queue的介紹

• 優(yōu)先級隊(duì)列是一種容器適配器，根據(jù)嚴(yán)格的弱排序標(biāo)準(zhǔn)，它的第一個(gè)元素總是它所包含的元素中最大的。

• 此上下文類似于堆，在堆中可以隨時(shí)插入元素，并且只能檢索最大堆元素（優(yōu)先級隊(duì)列中位于頂部的元素）。

• 優(yōu)先級隊(duì)列被實(shí)現(xiàn)為容器適配器，容器適配器即將特定容器類封裝作為其底層容器類，queue 提供一組特定的成員函數(shù)來訪問其元素。元素從特定容器的“尾部”彈出，其稱為優(yōu)先級隊(duì)列的頂部。

• 底層容器可以是任何標(biāo)準(zhǔn)容器類模板，也可以是其他特定設(shè)計(jì)的容器類。容器應(yīng)該可以通過隨機(jī)訪問、迭代器訪問，并支持以下操作：

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

  • size()：返回容器中有效元素的個(gè)數(shù)

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

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

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

• 標(biāo)準(zhǔn)容器類 vector 和 deque 滿足這些需求。默認(rèn)情況下，如果沒有為特定的 priority_queue 類實(shí)例化指定容器類，則使用 vector。

• 需要支持隨機(jī)訪問迭代器，以便始終在內(nèi)部保持堆結(jié)構(gòu)。容器適配器通過在需要時(shí)自動(dòng)調(diào)用算法函數(shù) make_heap、push_heap 和 pop_heap 來自動(dòng)完成次操作。

二、priority_queue的使用

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

小Tips：默認(rèn)情況下，priority_queue 是大堆（默認(rèn)第三個(gè)模板參數(shù)是 less）；如果在 priority_queue 中放自定義類型的數(shù)據(jù)，用戶需要在自定義類型中提供 > 或者 < 的重載。

2.1 數(shù)組中的第k個(gè)最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        //建一個(gè)大堆，向下調(diào)整建堆的時(shí)間復(fù)雜度是O（N）
        priority_queue<int> pq(nums.begin(), nums.end());
        //pop k-1次,時(shí)間復(fù)雜度是O(K*logN)
        while(--k)
        {
            pq.pop();
        }
        return pq.top();
    }
};

上面這種做法當(dāng) K 的值接近 N 的時(shí)候，它的時(shí)間復(fù)雜度就是 O(N*logN)，是不滿足題目要求的，下面再用另外一種方法來解決。

lass Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        //用前k個(gè)數(shù)建一個(gè)小堆
        priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
        //遍歷剩下的 N-k 個(gè)，比堆頂大就換進(jìn)去
        //時(shí)間復(fù)雜度是 (N-K)logN
        for(size_t i = k; i < nums.size(); i++)
        {
            if(nums[i] > pq.top())
            {
                pq.pop();
                pq.push(nums[i]);
            }
        }
        return pq.top();
    }
};

上面這種解法是先用數(shù)組中的前 K 個(gè)元素建一個(gè)小堆，然后從數(shù)組的第 K+1 個(gè)元素開始往后遍歷，遇到比堆頂元素大的就將堆頂?shù)脑?pop 出來，將當(dāng)前元素 push 進(jìn)去。建堆的時(shí)間復(fù)雜度是 O(K)，更新小堆的時(shí)間復(fù)雜度是 O((N-K)logK)，這種做法當(dāng) K 很小的時(shí)候時(shí)間復(fù)雜度可以近似看做 O(NlogK)，當(dāng) K 很大的時(shí)候，時(shí)間復(fù)雜度可以近似看做 O(logK)。

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

3.1 仿函數(shù)

仿函數(shù)本質(zhì)上一個(gè)類，之所以把它叫仿函數(shù)是因?yàn)檫@個(gè)類的對象可以像函數(shù)一樣去使用。舉例如下：

//一個(gè)仿函數(shù)
template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
int main()
{
	Less<int> lessfunc;//定義一個(gè)對象
	cout << lessfunc(1, 2) << endl;//該類型對象可以像函數(shù)一樣去使用
	//cout << lessfunc.operator()(1, 2) << endl;//和上面等價(jià)
	return 0;
}

小Tips：仿函數(shù)一般都是類模板，這樣就可以支持不同類型的大小比較，前提是該種類型重載實(shí)現(xiàn)了比較運(yùn)算符。仿函數(shù)的誕生是為了代替函數(shù)指針，函數(shù)指針的可讀性比較差。

3.2 成員變量

template<class T, class Container=std::vector<T>, class Compare = Less<T>>
	class priority_queue
	{
	public:
		//成員
	private:
		Container _con;
	};

小Tips：需要注意這里有三個(gè)模板參數(shù)，第一個(gè)模板參數(shù)表示要在優(yōu)先級隊(duì)列中存儲(chǔ)的數(shù)據(jù)類型；優(yōu)先級隊(duì)列本質(zhì)上也是一個(gè)容器適配器，所以第二個(gè)模板參數(shù)表示優(yōu)先級隊(duì)列要使用的底層容器；第三個(gè)模板參數(shù)是一個(gè)仿函數(shù)，用來進(jìn)行大小比較的，因?yàn)閮?yōu)先級隊(duì)列中會(huì)涉及到建大堆還是建小堆，中間會(huì)涉及到比較，如果沒有這個(gè)仿函數(shù)，那么大小比較就只能寫死了，這樣不太好。

3.3 成員函數(shù)

3.3.1 構(gòu)造函數(shù)

priority_queue()
{}
template<class InputeIterator>
priority_queue(InputeIterator first, InputeIterator last)
{
	//先將數(shù)據(jù)插入
	while (first != last)
	{
		_con.push_back(*first);
		++first;
	}
	//建堆,從最后一個(gè)非葉子節(jié)點(diǎn)開始向下調(diào)整
	for (int i = (_con.size() - 1) / 2; i >= 0; i--)
	{
		AdjustDown(i);
	}
}

小Tips：迭代器區(qū)間構(gòu)造函數(shù)是一個(gè)函數(shù)模板，只要是能支持 ++ 操作的迭代器區(qū)間都可以，即單向迭代器、雙向迭代器、隨機(jī)迭代都可以。其次將數(shù)據(jù)插入容器后還需要建堆，這里采用向下調(diào)整建堆，它的時(shí)間復(fù)雜度是 O(N)。

3.3.2 AdjustDown

void AdjustDown(int parent)
{
	Compare com;
	while (parent * 2 + 1 < (int)_con.size())
	{
		//找到最大的孩子
		int maxchild = parent * 2 + 1;
		if (maxchild + 1 < (int)_con.size() && com(_con[maxchild], _con[maxchild + 1]))
		{
			maxchild++;
		}
		//和父節(jié)點(diǎn)比較
		if (com(_con[parent], _con[maxchild]))
		{
			std::swap(_con[maxchild], _con[parent]);
			parent = maxchild;
		}
		else
		{
			break;
		}
	}
}

小Tips：在仿函數(shù)的加持下，向下調(diào)整代碼中的大小比較不再固定，建大堆和小堆這一份代碼就夠了，最終是大堆還是小堆是由仿函數(shù)來控制的。

3.3.3 push

void push(const T& val)
{
	_con.push_back(val);
	AdjustUp(_con.size() - 1);
}

小Tips：在優(yōu)先級隊(duì)列的尾部追加數(shù)據(jù)，會(huì)涉及到向上調(diào)整，向上調(diào)整的代碼如下所示。

3.3.4 AdjustUp

void AdjustUp(int child)
{
	Compare com;
	int parent = (child - 1) / 2;
	while (child > 0)//父親不會(huì)小于0，因此這里的判斷條件要用孩子大于0，孩子等于0說明已經(jīng)調(diào)整到根節(jié)點(diǎn)，就無需繼續(xù)調(diào)整了
	{
		if (com(_con[parent], _con[child]))
		{
			std::swap(_con[child], _con[parent]);
			child = parent;
			parent = (child - 1) / 2;//這里parent不會(huì)小于0
		}
		else
		{
			break;
		}
	}
}

3.3.5 pop

void pop()
{
	std::swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
	AdjustDown(0);
}

小Tips：優(yōu)先級隊(duì)列中出數(shù)據(jù)，出的是堆頂?shù)臄?shù)據(jù)，堆頂?shù)臄?shù)據(jù)也就是容器中的第一個(gè)數(shù)據(jù)，如果底層容器是 vector 那么堆頂?shù)臄?shù)據(jù)就是下標(biāo)為 0 的數(shù)據(jù)，出堆頂?shù)臄?shù)據(jù)不能直接使用頭刪，這樣會(huì)導(dǎo)致后面數(shù)據(jù)的父子關(guān)系全亂了。正確的做法是，將堆頂?shù)臄?shù)據(jù)和容器中的最后一個(gè)數(shù)據(jù)交換，然后執(zhí)行 pop_back 去刪除，最后還需要從根節(jié)點(diǎn)開始執(zhí)行一次向下調(diào)整，讓交換到堆頂?shù)臄?shù)據(jù)去到它應(yīng)該去的地方。

3.3.6 empty

bool empty()
{
	return _con.size() == 0;
}

3.3.7 size

size_t size()
{
	return _con.size();
}

以上就是C++優(yōu)先級隊(duì)列的使用指南與模擬實(shí)現(xiàn)的詳細(xì)內(nèi)容，更多關(guān)于C++優(yōu)先級隊(duì)列的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論