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

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

優先級隊列(Priority Queue)

隊列是一種特征為FIFO的數據結構，每次從隊列中取出的是最早加入隊列中的元素。但是，許多應用需要另一種隊列，每次從隊列中取出的應是具有最高優先權的元素，這種隊列就是優先級隊列(Priority Queue)，也稱為優先權隊列。

1. 優先級隊列的概念

優先級隊列的定義

優先級隊列是不同于先進先出隊列的另一種隊列。每次從隊列中取出的是具有最高優先權的元素。

優先級隊列的特點

•  優先級隊列是0個或多個元素的集合，每個元素都有一個優先權或值。

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

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

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

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

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

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

 2.優先級隊列的使用

頭文件：#include < queue >
優先級隊列默認是最大優先級隊列

接口介紹

測試代碼：

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;
}

測試結果：默認是最大優先級隊列，所以堆頂元素一直是最大的元素

如何將創建最小優先級隊列----
優先級隊列原型：
泛型介紹：T為優先級隊列存儲的數據類型；Container為優先級隊列中存儲數據的容器；Compare偽函數，決定是最大優先級隊列還是最小優先級隊列

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

創建最小優先級隊列：

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

測試結果：

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

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

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

測試結果：

應用場景：Top-K問題
數組中的第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.優先級隊列的實現

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

private:
	vector<T> con;

向下調整算法

向下調整算法用于優先級隊列的刪除接口的實現

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;
			}
		}
	}

向上調整算法

向上調整算法用于優先級隊列的插入接口的實現

//向上調整
	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. 將數據插入到容器的尾端

2. 進行向上調整算法，建成堆

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

pop()

• 將收尾數據進行交換

• 刪除末尾最后一個元素

• 進行向下調整算法，建成堆

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

top()、size()、empty()

都直接使用容器中的接口實現

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

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

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

測試結果：

但是我們的實現非常的死板，首先是不能創建最小優先級隊列，其次是不能像底層實現一樣，可以選擇多種容器來存儲數據來實現。

解決普通的優先級隊列的兩個問題

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

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

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

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

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

2、所需要的容器

private:
	Container con;

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

與之前代碼需要修改的地方
1、需要創建兩個仿函數類

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

//用于最小優先級隊列
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、利用仿函數，替代代碼中關鍵的比較的地方

測試結果：

完整代碼

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

//用于最小優先級隊列
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:
	//向下調整
	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;
			}
		}
	}

	//向上調整
	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;
};

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