C++ 容器適配器priority_queue的使用及實(shí)現(xiàn)代碼
優(yōu)先級隊(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)先級隊(duì)列(Priority Queue)，也稱為優(yōu)先權(quán)隊(duì)列。
1. 優(yōu)先級隊(duì)列的概念
優(yōu)先級隊(duì)列的定義
優(yōu)先級隊(duì)列是不同于先進(jìn)先出隊(duì)列的另一種隊(duì)列。每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素。
優(yōu)先級隊(duì)列的特點(diǎn)
- 優(yōu)先級隊(duì)列是0個(gè)或多個(gè)元素的集合，每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值。
- 當(dāng)給每個(gè)元素分配一個(gè)數(shù)字來標(biāo)記其優(yōu)先級時(shí)，可設(shè)較小的數(shù)字具有較高的優(yōu)先級，這樣更方便地在一個(gè)集合中訪問優(yōu)先級最高的元素，并對其進(jìn)行查找和刪除操作。
- 對優(yōu)先級隊(duì)列，執(zhí)行的操作主要有：(1)查找，(2)插入，(3)刪除。
- 在最小優(yōu)先級隊(duì)列(min Priority Queue)中，查找操作用來搜索優(yōu)先權(quán)最小的元素，刪除操作用來刪除該元素。
- 在最大優(yōu)先級隊(duì)列(max Priority Queue)中，查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素。
- 插入操作均只是簡單地把一個(gè)新的元素加入到隊(duì)列中。
- 注：每個(gè)元素的優(yōu)先級根據(jù)問題的要求而定。當(dāng)從優(yōu)先級隊(duì)列中刪除一個(gè)元素時(shí)，可能出現(xiàn)多個(gè)元素具有相同的優(yōu)先權(quán)。在這種情況下，把這些具有相同優(yōu)先權(quán)的元素視為一個(gè)先來先服務(wù)的隊(duì)列，按他們的入隊(duì)順序進(jìn)行先后處理。
2.優(yōu)先級隊(duì)列的使用
頭文件：#include < queue >
優(yōu)先級隊(duì)列默認(rèn)是最大優(yōu)先級隊(duì)列
接口介紹
| 函數(shù)聲明 | 函數(shù)說明 |
|---|---|
| priority_queue() / priority_queue(first, last) | 構(gòu)造一個(gè)空的優(yōu)先級隊(duì)列 |
| empty( ) | 判斷優(yōu)先級隊(duì)列是否為空，為空返回true |
| empty( ) | 判斷優(yōu)先級隊(duì)列是否為空，為空返回true |
| top( ) | 獲取優(yōu)先級隊(duì)列中最大或者最小的元素，即堆頂元素 |
| push(x) | 將x元素插入到優(yōu)先級隊(duì)列中 |
| pop() | 刪除優(yōu)先級隊(duì)列中最大或者最小的元素， 即刪除堆頂元素 |
測試代碼：
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é)果：默認(rèn)是最大優(yōu)先級隊(duì)列，所以堆頂元素一直是最大的元素
如何將創(chuàng)建最小優(yōu)先級隊(duì)列----
優(yōu)先級隊(duì)列原型：
泛型介紹：T為優(yōu)先級隊(duì)列存儲(chǔ)的數(shù)據(jù)類型；Container為優(yōu)先級隊(duì)列中存儲(chǔ)數(shù)據(jù)的容器；Compare偽函數(shù)，決定是最大優(yōu)先級隊(duì)列還是最小優(yōu)先級隊(duì)列
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;
創(chuàng)建最小優(yōu)先級隊(duì)列：
priority_queue<int, vector<int>, greater<int>> pq;
測試結(jié)果：
優(yōu)先級隊(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;
};
測試結(jié)果：
應(yī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)先級隊(duì)列的實(shí)現(xiàn)
標(biāo)準(zhǔn)容器類vector和deque(雙端隊(duì)列)滿足實(shí)現(xiàn)優(yōu)先級隊(duì)列的需求，庫中底層默認(rèn)是使用Vector容器來實(shí)現(xiàn)的，我們現(xiàn)在就利用vector簡單模擬實(shí)現(xiàn)
private: vector<T> con;
向下調(diào)整算法
向下調(diào)整算法用于優(yōu)先級隊(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)先級隊(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();
}
測試結(jié)果：
但是我們的實(shí)現(xiàn)非常的死板，首先是不能創(chuàng)建最小優(yōu)先級隊(duì)列，其次是不能像底層實(shí)現(xiàn)一樣，可以選擇多種容器來存儲(chǔ)數(shù)據(jù)來實(shí)現(xiàn)。
解決普通的優(yōu)先級隊(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)先級隊(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)先級隊(duì)列
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
//用于最小優(yōu)先級隊(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)鍵的比較的地方
測試結(jié)果：
完整代碼
//用大最小優(yōu)先級隊(duì)列
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
//用于最小優(yōu)先級隊(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)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- c++ priority_queue用法入門超詳細(xì)教程
- C++ 中"priority_queue" 優(yōu)先級隊(duì)列實(shí)例詳解
- c++中priority_queue模擬的實(shí)現(xiàn)
- 深入了解C++優(yōu)先隊(duì)列(priority_queue)的使用方法
- C++中priority_queue與仿函數(shù)實(shí)現(xiàn)方法
- C++中STL的優(yōu)先隊(duì)列priority_queue詳解
- C++中priority_queue模擬實(shí)現(xiàn)的代碼示例
- 詳解c++優(yōu)先隊(duì)列priority_queue的用法
- 詳解C++模擬實(shí)現(xiàn)priority_queue(仿函數(shù))
- C++深入刨析優(yōu)先級隊(duì)列priority_queue的使用
- C++中priority_queue的實(shí)現(xiàn)
相關(guān)文章
C++中constexpr 與 explicit關(guān)鍵字使用實(shí)戰(zhàn)樣例
文章詳細(xì)介紹了constexpr和explicit關(guān)鍵字在C++中的用途和用法,constexpr用于聲明實(shí)體可以在編譯期求值,而explicit用于阻止不期望的隱式類型轉(zhuǎn)換,本文結(jié)合實(shí)例代碼介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2025-12-12
這篇文章主要介紹了C++ new-handler機(jī)制的相關(guān)資料，幫助大家更好的理解和使用c++，感興趣的朋友可以了解下2020-11-11
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)拼圖游戲源碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了二叉樹前序遍歷的非遞歸算法,需要的朋友可以參考下2014-02-02
簡單介紹C語言中的umask()函數(shù)和truncate()函數(shù)
這篇文章主要介紹了簡單介紹C語言中的umask()函數(shù)和truncate()函數(shù),是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
這篇文章主要為大家詳細(xì)介紹了C++利用鏈棧實(shí)現(xiàn)表達(dá)式求值的相關(guān)資料，感興趣的小伙伴們可以參考一下2016-05-05
C++多線程實(shí)現(xiàn)TCP服務(wù)器端同時(shí)和多個(gè)客戶端通信
通訊建立后首先由服務(wù)器端發(fā)送消息，客戶端接收消息；接著客戶端發(fā)送消息，服務(wù)器端接收消息，實(shí)現(xiàn)交互發(fā)送消息。本文主要介紹了C++多線程實(shí)現(xiàn)TCP服務(wù)器端同時(shí)和多個(gè)客戶端通信，感興趣的可以了解一下2021-05-05
C語言數(shù)據(jù)結(jié)構(gòu)之Hash散列表
這篇文章主要介紹了C語言數(shù)據(jù)結(jié)構(gòu)之Hash散列表,散列表(哈希表)其思想主要是基于數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù),時(shí)間復(fù)雜度為O(1)的特性,可以說是數(shù)組的一種拓展,需要的朋友可以參考下2023-08-08
本文主要介紹了C語言楊氏矩陣中查找元素的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-07-07
本文主要介紹C 語言中的switch 語句,這里提供示例代碼和詳細(xì)介紹,希望能幫助學(xué)習(xí)C語言的小伙伴2016-07-07