C++ 容器適配器priority_queue怎么用

這篇文章給大家分享的是有關(guān)C++ 容器適配器priority_queue怎么用的內(nèi)容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

優(yōu)先級隊列(Priority Queue)

隊列是一種特征為FIFO的數(shù)據(jù)結(jié)構(gòu)，每次從隊列中取出的是最早加入隊列中的元素。但是，許多應(yīng)用需要另一種隊列，每次從隊列中取出的應(yīng)是具有最高優(yōu)先權(quán)的元素，這種隊列就是優(yōu)先級隊列(Priority Queue)，也稱為優(yōu)先權(quán)隊列。

1. 優(yōu)先級隊列的概念

優(yōu)先級隊列的定義

優(yōu)先級隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素。

優(yōu)先級隊列的特點

•  優(yōu)先級隊列是0個或多個元素的集合，每個元素都有一個優(yōu)先權(quán)或值。

• 當(dāng)給每個元素分配一個數(shù)字來標記其優(yōu)先級時，可設(shè)較小的數(shù)字具有較高的優(yōu)先級，這樣更方便地在一個集合中訪問優(yōu)先級最高的元素，并對其進行查找和刪除操作。

• 對優(yōu)先級隊列，執(zhí)行的操作主要有：(1)查找，(2)插入，(3)刪除。

• 在最小優(yōu)先級隊列(min Priority Queue)中，查找操作用來搜索優(yōu)先權(quán)最小的元素，刪除操作用來刪除該元素。

• 在最大優(yōu)先級隊列(max Priority Queue)中，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素。

• 插入操作均只是簡單地把一個新的元素加入到隊列中。

• 注：每個元素的優(yōu)先級根據(jù)問題的要求而定。當(dāng)從優(yōu)先級隊列中刪除一個元素時，可能出現(xiàn)多個元素具有相同的優(yōu)先權(quán)。在這種情況下，把這些具有相同優(yōu)先權(quán)的元素視為一個先來先服務(wù)的隊列，按他們的入隊順序進行先后處理。

 2.優(yōu)先級隊列的使用

頭文件：#include < queue >
優(yōu)先級隊列默認是最大優(yōu)先級隊列

接口介紹

測試代碼：

void test()
{
	priority_queue<int> pq;
	pq.push(13);
	pq.push(14);
	pq.push(9);
	pq.push(23);
	pq.push(12);
	pq.push(22);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

測試結(jié)果：默認是最大優(yōu)先級隊列，所以堆頂元素一直是最大的元素

如何將創(chuàng)建最小優(yōu)先級隊列----
優(yōu)先級隊列原型：
泛型介紹：T為優(yōu)先級隊列存儲的數(shù)據(jù)類型；Container為優(yōu)先級隊列中存儲數(shù)據(jù)的容器；Compare偽函數(shù)，決定是最大優(yōu)先級隊列還是最小優(yōu)先級隊列

template <class T, class Container = vector<T>,
  class Compare = less<typename Container::value_type> > class priority_queue;

創(chuàng)建最小優(yōu)先級隊列：

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

測試結(jié)果：

優(yōu)先級隊列存放自定義類型時，需要自定義類型支持比較的操作。

class A
{
public:
	A(int a = 1)
		:_a(a)
	{}

	//支持比較函數(shù)
	bool operator<(const A& a) const
	{
		return _a < a._a;
	}
	bool operator>(const A& a) const
	{
		return _a > a._a;
	}
	int _a;
};

測試結(jié)果：

應(yīng)用場景：Top-K問題
數(shù)組中的第K個最大元素
代碼：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int> pq(nums.begin(), nums.end());
        while (--k)
            pq.pop();
        return pq.top();
    }
};

3.優(yōu)先級隊列的實現(xiàn)

標準容器類vector和deque(雙端隊列)滿足實現(xiàn)優(yōu)先級隊列的需求，庫中底層默認是使用Vector容器來實現(xiàn)的，我們現(xiàn)在就利用vector簡單模擬實現(xiàn)

private:
	vector<T> con;

向下調(diào)整算法

向下調(diào)整算法用于優(yōu)先級隊列的刪除接口的實現(xiàn)

void shiftDown()
	{
		int parent = 0;
		int child = 2 * parent + 1;
		while (child < con.size())
		{
			if (child + 1 < con.size() && con[child] < con[child + 1])
			{
				++child;
			}
			if (con[parent] < con[child])
			{
				swap(con[parent], con[child]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}

向上調(diào)整算法

向上調(diào)整算法用于優(yōu)先級隊列的插入接口的實現(xiàn)

//向上調(diào)整
	void shiftUp(int child)
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (con[parent] < con[child])
			{
				swap(con[parent], con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

push()

1. 將數(shù)據(jù)插入到容器的尾端

2. 進行向上調(diào)整算法，建成堆

	void push(const T& val)
	{
		//尾插
		con.push_back(val);
		shiftUp(con.size() - 1);
	}

pop()

• 將收尾數(shù)據(jù)進行交換

• 刪除末尾最后一個元素

• 進行向下調(diào)整算法，建成堆

	void pop()
	{
		//交換
		swap(con[0], con[con.size() - 1]);
		con.pop_back();
		shiftDown();
	}

top()、size()、empty()

都直接使用容器中的接口實現(xiàn)

T& top()
	{
		return con.front();
	}

	size_t size() const
	{
		return con.size();
	}

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

測試結(jié)果：

但是我們的實現(xiàn)非常的死板，首先是不能創(chuàng)建最小優(yōu)先級隊列，其次是不能像底層實現(xiàn)一樣，可以選擇多種容器來存儲數(shù)據(jù)來實現(xiàn)。

解決普通的優(yōu)先級隊列的兩個問題

解決只能通過vector< T >來存儲數(shù)據(jù)的問題
我們可以通過容器多添加一個泛型來解決多種容器的存儲
priority_queue可以通過 vector< T >、deque< T >實現(xiàn)
默認使用vector< T >
原因：

• list不支持隨機訪問迭代器的方式來訪問元素

• 與deque相比：deque隨機訪問效率低于vector

與之前代碼需要修改的地方
1、泛型

template<class T, class Container = vector<T>>

2、所需要的容器

private:
	Container con;

解決只能創(chuàng)建最大優(yōu)先級隊列問題
解決辦法，加入新的泛型，該泛型是一個偽函數(shù)
如果不知道什么是偽函數(shù)，可以看看什么是偽函數(shù)，以及偽函數(shù)的使用
大小堆創(chuàng)建的不同其實就是在實現(xiàn)向上調(diào)整和向下調(diào)整時元素比較的不同而已。

與之前代碼需要修改的地方
1、需要創(chuàng)建兩個仿函數(shù)類

//用大最小優(yōu)先級隊列
template<class T>
struct Less
{
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

//用于最小優(yōu)先級隊列
template<class T>
struct Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

2、加入新泛型

template<class T, class Container = vector<T>, class Compare = Less<T>>

private:
	Compare cmp;

3、利用仿函數(shù)，替代代碼中關(guān)鍵的比較的地方

測試結(jié)果：

完整代碼

//用大最小優(yōu)先級隊列
template<class T>
struct Less
{
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

//用于最小優(yōu)先級隊列
template<class T>
struct Greater
{
	bool operator()(const T& a, const T& b)
	{
		return a > b;
	}
};

template<class T, class Container = vector<T>, class Compare = Less<T>>
class PriorityQueue
{
public:
	//向下調(diào)整
	void shiftDown()
	{
		int parent = 0;
		int child = 2 * parent + 1;
		while (child < con.size())
		{
			if (child + 1 < con.size() && cmp(con[child], con[child + 1]))
			{
				++child;
			}
			if (cmp(con[parent], con[child]))
			{
				swap(con[parent], con[child]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}

	//向上調(diào)整
	void shiftUp(int child)
	{
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			if (cmp(con[parent], con[child]))
			{
				swap(con[parent], con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void push(const T& val)
	{
		//尾插
		con.push_back(val);
		shiftUp(con.size() - 1);
	}

	void pop()
	{
		//交換
		swap(con[0], con[con.size() - 1]);
		con.pop_back();
		shiftDown();
	}

	T& top()
	{
		return con.front();
	}

	size_t size() const
	{
		return con.size();
	}

	bool empty() const
	{
		return con.empty();
	}
private:
	Container con;
	Compare cmp;
};

感謝各位的閱讀！關(guān)于“C++ 容器適配器priority_queue怎么用”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！