C++ 容器適配器priority_queue的使用及實(shí)現(xiàn)代碼
優(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)，也稱(chēng)為優(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ù)字來(lái)標(biāo)記其優(yōu)先級(jí)時(shí)，可設(shè)較小的數(shù)字具有較高的優(yōu)先級(jí)，這樣更方便地在一個(gè)集合中訪(fǎng)問(wèn)優(yōu)先級(jí)最高的元素，并對(duì)其進(jìn)行查找和刪除操作。
- 對(duì)優(yōu)先級(jí)隊(duì)列，執(zhí)行的操作主要有：(1)查找，(2)插入，(3)刪除。
- 在最小優(yōu)先級(jí)隊(duì)列(min Priority Queue)中，查找操作用來(lái)搜索優(yōu)先權(quán)最小的元素，刪除操作用來(lái)刪除該元素。
- 在最大優(yōu)先級(jí)隊(duì)列(max Priority Queue)中，查找操作用來(lái)搜索優(yōu)先權(quán)最大的元素，刪除操作用來(lái)刪除該元素。
- 插入操作均只是簡(jiǎn)單地把一個(gè)新的元素加入到隊(duì)列中。
- 注：每個(gè)元素的優(yōu)先級(jí)根據(jù)問(wèn)題的要求而定。當(dāng)從優(yōu)先級(jí)隊(duì)列中刪除一個(gè)元素時(shí)，可能出現(xiàn)多個(gè)元素具有相同的優(yōu)先權(quán)。在這種情況下，把這些具有相同優(yōu)先權(quán)的元素視為一個(gè)先來(lái)先服務(wù)的隊(duì)列，按他們的入隊(duì)順序進(jìn)行先后處理。
2.優(yōu)先級(jí)隊(duì)列的使用
頭文件：#include < queue >
優(yōu)先級(jí)隊(duì)列默認(rèn)是最大優(yōu)先級(jí)隊(duì)列
接口介紹
| 函數(shù)聲明 | 函數(shù)說(shuō)明 |
|---|---|
| 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ù)類(lèi)型；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ì)列存放自定義類(lèi)型時(shí)，需要自定義類(lèi)型支持比較的操作。
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問(wèn)題
數(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)容器類(lèi)vector和deque(雙端隊(duì)列)滿(mǎn)足實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列的需求，庫(kù)中底層默認(rèn)是使用Vector容器來(lái)實(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)一樣，可以選擇多種容器來(lái)存儲(chǔ)數(shù)據(jù)來(lái)實(shí)現(xiàn)。
解決普通的優(yōu)先級(jí)隊(duì)列的兩個(gè)問(wèn)題
解決只能通過(guò)vector< T >來(lái)存儲(chǔ)數(shù)據(jù)的問(wèn)題
我們可以通過(guò)容器多添加一個(gè)泛型來(lái)解決多種容器的存儲(chǔ)
priority_queue可以通過(guò) vector< T >、deque< T >實(shí)現(xiàn)
默認(rèn)使用vector< T >
原因：
- list不支持隨機(jī)訪(fǎng)問(wèn)迭代器的方式來(lái)訪(fǎng)問(wèn)元素
- 與deque相比：deque隨機(jī)訪(fǎng)問(wèn)效率低于vector
與之前代碼需要修改的地方
1、泛型
template<class T, class Container = vector<T>>
2、所需要的容器
private: Container con;
解決只能創(chuàng)建最大優(yōu)先級(jí)隊(duì)列問(wèn)題
解決辦法，加入新的泛型，該泛型是一個(gè)偽函數(shù)
如果不知道什么是偽函數(shù)，可以看看什么是偽函數(shù)，以及偽函數(shù)的使用
大小堆創(chuàng)建的不同其實(shí)就是在實(shí)現(xiàn)向上調(diào)整和向下調(diào)整時(shí)元素比較的不同而已。
與之前代碼需要修改的地方
1、需要?jiǎng)?chuàng)建兩個(gè)仿函數(shù)類(lèi)
//用大最小優(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)文章希望大家以后多多支持腳本之家！
相關(guān)文章
利用C++實(shí)現(xiàn)矩陣的相加/相稱(chēng)/轉(zhuǎn)置/求鞍點(diǎn)
利用C++實(shí)現(xiàn)矩陣的相加/相稱(chēng)/轉(zhuǎn)置/求鞍點(diǎn)。需要的朋友可以過(guò)來(lái)參考下，希望對(duì)大家有所幫助2013-10-10
這篇文章主要為大家介紹了C++?opencv實(shí)現(xiàn)幾何圖形的繪制示例實(shí)現(xiàn)代碼，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
異常是面向?qū)ο笳Z(yǔ)言常用的一種處理錯(cuò)誤的方式，當(dāng)一個(gè)函數(shù)發(fā)現(xiàn)自己無(wú)法處理的錯(cuò)誤時(shí)就可以?huà)伋霎惓?，本文我們將?duì)C++ 異常機(jī)制進(jìn)行深入剖析，感興趣的同學(xué)跟著小編一起來(lái)看看吧2023-07-07
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言代碼實(shí)現(xiàn)2048游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
c++打印封裝每次打印前面加上時(shí)間戳問(wèn)題
這篇文章主要介紹了c++打印封裝每次打印前面加上時(shí)間戳問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-01-01
C語(yǔ)言 動(dòng)態(tài)分配數(shù)組案例詳解
這篇文章主要介紹了C語(yǔ)言 動(dòng)態(tài)分配數(shù)組案例詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
大家好，本篇文章主要講的是C語(yǔ)言數(shù)組詳細(xì)介紹，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話(huà)記得收藏一下，方便下次瀏覽2022-01-01
這篇文章主要介紹了EasyC++靜態(tài)持續(xù)變量，除了自動(dòng)存儲(chǔ)變量之后，C++當(dāng)中還有靜態(tài)持續(xù)變量。關(guān)于靜態(tài)持續(xù)變量的定義C++和C語(yǔ)言是一樣的，它擁有三種鏈接性，即外部鏈接性、內(nèi)部連接性和無(wú)鏈接性，下面一起進(jìn)入文章了解更具體內(nèi)容吧2021-12-12
詳解C++編程中向函數(shù)傳遞引用參數(shù)的用法
這篇文章主要介紹了詳解C++編程中向函數(shù)傳遞引用參數(shù)的用法,包括使函數(shù)返回引用類(lèi)型以及對(duì)指針的引用,需要的朋友可以參考下2016-01-01