腳本之家服務器常用軟件

快捷導航

C++ 容器適配器priority_queue的使用及實現(xiàn)代碼

更新時間：2021年04月21日 10:25:45 作者：WhiteShirtI

這篇文章主要介紹了C++ 容器適配器priority_queue的使用及實現(xiàn),本文通過實例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下

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

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

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

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

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

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

優(yōu)先級隊列是0個或多個元素的集合，每個元素都有一個優(yōu)先權或值。
當給每個元素分配一個數(shù)字來標記其優(yōu)先級時，可設較小的數(shù)字具有較高的優(yōu)先級，這樣更方便地在一個集合中訪問優(yōu)先級最高的元素，并對其進行查找和刪除操作。
對優(yōu)先級隊列，執(zhí)行的操作主要有：(1)查找，(2)插入，(3)刪除。
在最小優(yōu)先級隊列(min Priority Queue)中，查找操作用來搜索優(yōu)先權最小的元素，刪除操作用來刪除該元素。
在最大優(yōu)先級隊列(max Priority Queue)中，查找操作用來搜索優(yōu)先權最大的元素，刪除操作用來刪除該元素。
插入操作均只是簡單地把一個新的元素加入到隊列中。
注：每個元素的優(yōu)先級根據(jù)問題的要求而定。當從優(yōu)先級隊列中刪除一個元素時，可能出現(xiàn)多個元素具有相同的優(yōu)先權。在這種情況下，把這些具有相同優(yōu)先權的元素視為一個先來先服務的隊列，按他們的入隊順序進行先后處理。

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

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

接口介紹

函數(shù)聲明	函數(shù)說明
priority_queue() / priority_queue(first, last)	構造一個空的優(yōu)先級隊列
empty( )	判斷優(yōu)先級隊列是否為空，為空返回true
empty( )	判斷優(yōu)先級隊列是否為空，為空返回true
top( )	獲取優(yōu)先級隊列中最大或者最小的元素，即堆頂元素
push(x)	將x元素插入到優(yōu)先級隊列中
pop()	刪除優(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;
}

測試結果：默認是最大優(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;

測試結果：

在這里插入圖片描述

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

測試結果：

在這里插入圖片描述

應用場景：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;

向下調整算法

向下調整算法用于優(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;
			}
		}
	}

向上調整算法

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

//向上調整
	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()

將數(shù)據(jù)插入到容器的尾端
進行向上調整算法，建成堆

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

pop()

將收尾數(shù)據(jù)進行交換
刪除末尾最后一個元素
進行向下調整算法，建成堆

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

測試結果：

在這里插入圖片描述

但是我們的實現(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)向上調整和向下調整時元素比較的不同而已。

與之前代碼需要修改的地方
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ù)，替代代碼中關鍵的比較的地方

在這里插入圖片描述

測試結果：

在這里插入圖片描述

完整代碼

//用大最小優(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:
	//向下調整
	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的使用及實現(xiàn)的文章就介紹到這了,更多相關C++ 容器適配器priority_queue內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: