快捷導(dǎo)航

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

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

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

優(yōu)先級(jí)隊(duì)列(Priority Queue)

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

1. 優(yōu)先級(jí)隊(duì)列的概念

優(yōu)先級(jí)隊(duì)列的定義

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

優(yōu)先級(jí)隊(duì)列的特點(diǎn)

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

2.優(yōu)先級(jí)隊(duì)列的使用

頭文件：#include < queue >
優(yōu)先級(jí)隊(duì)列默認(rèn)是最大優(yōu)先級(jí)隊(duì)列

接口介紹

函數(shù)聲明	函數(shù)說明
priority_queue() / priority_queue(first, last)	構(gòu)造一個(gè)空的優(yōu)先級(jí)隊(duì)列
empty( )	判斷優(yōu)先級(jí)隊(duì)列是否為空，為空返回true
empty( )	判斷優(yōu)先級(jí)隊(duì)列是否為空，為空返回true
top( )	獲取優(yōu)先級(jí)隊(duì)列中最大或者最小的元素，即堆頂元素
push(x)	將x元素插入到優(yōu)先級(jí)隊(duì)列中
pop()	刪除優(yōu)先級(jí)隊(duì)列中最大或者最小的元素，即刪除堆頂元素

測(cè)試代碼：

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

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

在這里插入圖片描述

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

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

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

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

測(cè)試結(jié)果：

在這里插入圖片描述

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

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

測(cè)試結(jié)果：

在這里插入圖片描述

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

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)先級(jí)隊(duì)列的實(shí)現(xiàn)

標(biāo)準(zhǔn)容器類vector和deque(雙端隊(duì)列)滿足實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的需求，庫中底層默認(rèn)是使用Vector容器來實(shí)現(xiàn)的，我們現(xiàn)在就利用vector簡(jiǎn)單模擬實(shí)現(xiàn)

private:
	vector<T> con;

向下調(diào)整算法

向下調(diào)整算法用于優(yōu)先級(jí)隊(duì)列的刪除接口的實(shí)現(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)先級(jí)隊(duì)列的插入接口的實(shí)現(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()

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

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

pop()

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

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

top()、size()、empty()

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

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

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

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

測(cè)試結(jié)果：

在這里插入圖片描述

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

解決普通的優(yōu)先級(jí)隊(duì)列的兩個(gè)問題

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

list不支持隨機(jī)訪問迭代器的方式來訪問元素
與deque相比：deque隨機(jī)訪問效率低于vector

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

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

2、所需要的容器

private:
	Container con;

在這里插入圖片描述

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

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

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

//用于最小優(yōu)先級(jí)隊(duì)列
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)鍵的比較的地方

在這里插入圖片描述

測(cè)試結(jié)果：

在這里插入圖片描述

完整代碼

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

//用于最小優(yōu)先級(jí)隊(duì)列
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的使用及實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ 容器適配器priority_queue內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: