昆明網(wǎng)站建設公司_百度推廣怎么提高關鍵詞排名
文章目錄
- 一、priority_queue類簡介
- 二、priority_queue類常用接口
- 三、priority_queue類的使用
- 四、STL中priority_queue類的模擬實現(xiàn)
一、priority_queue類簡介
- 優(yōu)先隊列是一種容器適配器,根據(jù)嚴格的弱排序標準,它的第一個元素總是它所包含的元素中最大的。
- 類似于堆,在堆中可以隨時插入元素,并且只能檢索最大堆元素(優(yōu)先隊列中位于頂部的元素)。
- 優(yōu)先隊列被實現(xiàn)為容器適配器,容器適配器即將特定容器類封裝作為其底層容器類。元素從特定容器的“尾部”彈出,其稱為優(yōu)先隊列的頂部。
- 底層容器可以是任何標準容器類模板,也可以是其他特定設計的容器類。容器應該可以通過隨機訪問迭代器訪問,并支持以下操作:
empty() 檢測容器是否為空
,size():返回容器中有效元素個數(shù)
,front():返回容器中第一個元素的引用
,push_back():在容器尾部插入元素
,pop_back():刪除容器尾部元素
。 - 標準容器類vector和deque滿足這些需求。默認情況下,如果沒有為特定的priority_queue類實例化指定容器類,則使用vector。
- 需要支持隨機訪問迭代器,以便始終在內部保持堆結構。容器適配器通過在需要時自動調用算法函數(shù)make_heap、push_heap和pop_heap來自動完成此操作。
??以上內容來自:www.cplusplus.com priority_queue類文檔的介紹,在STL的學習中,推薦大家看這個文檔,對每個類都有詳細的介紹。
總結
??優(yōu)先級隊列 (priority_queue) 屬于STL中的容器適配器,其底層存儲數(shù)據(jù)的容器默認使用vector,并且使用堆算法使得vector中的元素構造成堆的結構。所以,可以說優(yōu)先級隊列 (priority_queue) 就是堆,默認情況下是大堆。在使用時,與queue相同,要引入頭文件#include<queue>
。
二、priority_queue類常用接口
函數(shù)名稱 | 功能說明 |
---|---|
priority_queue() | 構造一個空的優(yōu)先級隊列 |
priority_queue(first,last) | 構造一個空的優(yōu)先級隊列 |
empty() | 檢測優(yōu)先級隊列是否為空,是返回true,否則返回false |
top( ) | 返回優(yōu)先級隊列中最大/最小元素,即堆頂元素 |
push(X) | 在優(yōu)先級隊列中插入元素X |
pop() | 刪除優(yōu)先級隊列中最大/最小元素,即堆頂元素 |
priority_queue類常用接口應用
#include<iostream>
#include<queue>
#include<vector>
#include<functional>
using namespace std;int main()
{vector<int> v = { 10,60,50,20 };//priority_queue<int> pq;priority_queue<int> pq(v.begin(),v.end());pq.push(30);while (!pq.empty()){cout<< pq.top()<<" ";pq.pop();}return 0;
}
三、priority_queue類的使用
切換大小堆
?? 默認情況下,priority_queue是創(chuàng)建的是大堆,其底層按照小于號比較,默認模板參數(shù)為template<class T, class Container =std::vector<T>, class Compare = std::less<T>>
;如果要創(chuàng)建小堆,將第三個模板參數(shù)換成greater即可,例如priority_queue<int, vector<int>, greater<int>> pq2(v.begin(), v.end());
greater<int>
和less<T>
??greater和less的頭文件為#include <functional>
,具體實現(xiàn)見第三節(jié)模擬實現(xiàn)部分。 <functional>
是C++標準庫中的一個頭文件,定義了C++標準中多個用于表示函數(shù)對象的類模板,包括算法操作、比較操作、邏輯操作;
??建堆時,less<T>
是大頂堆,堆元素是從大到小;greater<T>
是小頂堆,堆元素是從小到大。
??排序時,less<T>
是升序,數(shù)組元素是從小到大;greater<T>
是降序堆,數(shù)組元素是從大到小。
如果priority_queue中放自定義類型的數(shù)據(jù),需要在自定義類型中提供> 或者< 的重載
class Date
{
public:Date(int year = 2023, int month = 1, int day = 1): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}friend ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}
private:int _year;int _month;int _day;
};void TestPriorityQueue()
{// 大堆,需要用戶在自定義類型中提供<的重載priority_queue<Date> q1;q1.push(Date(2023, 1, 2));q1.push(Date(2023, 1, 3));q1.push(Date(2023, 1, 4));cout << q1.top() << endl;// 如果要創(chuàng)建小堆,需要用戶提供>的重載priority_queue<Date, vector<Date>, greater<Date>> q2;q2.push(Date(2023, 1, 2));q2.push(Date(2023, 1, 3));q2.push(Date(2023, 1, 4));cout << q2.top() << endl;
}
四、STL中priority_queue類的模擬實現(xiàn)
#pragma once
#include<vector>namespace MyPriority_queue
{template<class T>struct less{bool operator()(const T& l, const T& r){return l < r;}};template<class T>struct greater{bool operator()(const T& l, const T& r){return l > r;}};template<class T, class Container =std::vector<T>, class Compare = std::less<T>>class priority_queue{public://typedef typename Container::value_type VT;void AdjustUp(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0){//if (_con[parent] > _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);AdjustUp(_con.size() - 1);}void AdjustDwon(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//if (child+1 < _con.size() && _con[child] > _con[child+1])if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}//if (_con[parent] > _con[child])if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDwon(0);}T top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};
}