c++ priority_queue用法入門超詳細教程
更新時間：2023年12月06日 11:14:52 作者：舊林墨煙
priority_queue即優(yōu)先級隊列,它的使用場景很多,它底層是用大小根堆實現(xiàn)的,可以用log(n)的時間動態(tài)地維護數(shù)據(jù)的有序性,這篇文章主要介紹了c++ priority_queue用法入門超詳細教程,需要的朋友可以參考下
1、priority_queue的作用
priority_queue即優(yōu)先級隊列，它的使用場景很多，它底層是用大小根堆實現(xiàn)的，可以用log(n)的時間動態(tài)地維護數(shù)據(jù)的有序性。適用于許多場景，比如簡化哈夫曼樹算法、dijkstra算法等等
priority_queue是不允許隨機訪問，只能訪問隊列首部的元素，也只能對首部元素進行出隊，下面進行學習它的基本用法
2、priority_queue的定義
頭文件
#include<queue>
基本定義方法：
基本定義默認是使用大頂堆的，即隊首總是最大的元素
priority_queue<儲存的類型> 容器名
如：
priority_queue<int> q;//儲存int型數(shù)據(jù) priority_queue<double> q;//儲存double型數(shù)據(jù) priority_queue<string> q;//儲存string型數(shù)據(jù) priority_queue<結構體名> q;//儲存結構體或者類
快速切換大小頂堆定義：
less<儲存的數(shù)據(jù)類型> 即使用大頂堆
greater<儲存的數(shù)據(jù)類型> 即是用小頂堆
priority_queue<儲存的類型,vector<儲存的類型>,頂堆的類型> 容器名
如：
使用大頂堆的隊列：
priority_queue<int,vector<int>,less<int>> q;//儲存int型數(shù)據(jù) priority_queue<double,vector<double>,less<double>> q;//儲存double型數(shù)據(jù) priority_queue<string,vector<string>,less<string>> q;//儲存string型數(shù)據(jù) priority_queue<結構體名,vector<結構體名>,less<結構體名>> q;//儲存結構體或者類
使用小頂堆的隊列：
priority_queue<int,vector<int>,greater<int>> q;//儲存int型數(shù)據(jù) priority_queue<double,vector<double>,greater<double>> q;//儲存double型數(shù)據(jù) priority_queue<string,vector<string>,greater<string>> q;//儲存string型數(shù)據(jù) priority_queue<結構體名,vector<結構體名>,greater<結構體名>> q;//儲存結構體或者類
使用結構體重載運算符定義：
新建一個結構體，通過重載運算符改變頂堆的排序，這里是拓展用法，也是必學用法，因為自己寫的結構體是沒有比較大小功能的，當然也可以在原本的結構體里面重載運算符
priority_queue<int,vector<int>,cmp> q;//儲存int型數(shù)據(jù) priority_queue<double,vector<double>,cmp> q;//儲存double型數(shù)據(jù) priority_queue<string,vector<string>,cmp> q;//儲存string型數(shù)據(jù) priority_queue<結構體名,vector<結構體名>,cmp> q;//儲存結構體或者類
3、priority_queue的成員函數(shù)
empty() 如果優(yōu)先隊列為空，則返回真 pop() 刪除第一個元素 push() 加入一個元素 size() 返回優(yōu)先隊列中擁有的元素的個數(shù) top() 返回優(yōu)先隊列中有最高優(yōu)先級的元素
4、priority_queue的基本用法
普通數(shù)據(jù)類型的使用方法：
示例代碼：
#include<iostream>//c++標準頭文件，可以使用cout,cin等標準庫函數(shù)
#include<queue>//使用priority_queue時需要的頭文件
using namespace std;//命名空間，防止重名給程序帶來各種隱患，使用cin,cout,stack,map,set,vector,queue時都要使用
int main(){
priority_queue<int> q1;//定義一個默認大頂堆的優(yōu)先級隊列q1，即隊首元素總是最大值
// priority_queue<int,vector<int>,less<int>> q1; //這樣顯示定義大頂堆也是可以的
cout<<"定義默認大頂堆q1: priority_queue<int> q1"<<endl;
q1.push(10);//添加一個元素10
q1.push(5);//添加一個元素5
q1.push(7);//添加一個元素7
cout<<"按順序插入10、5、7這三個數(shù)據(jù)，目前優(yōu)先級隊列中的元素：10 5 7"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;//查看目前隊列中元素個數(shù)
cout<<"q1.empty()="<<q1.empty()<<endl;//查看目前隊列是否為空，1即為空，0即非空
cout<<"q1.top()="<<q1.top()<<endl;//查看目前隊列首部元素
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前優(yōu)先級隊列中的元素：5 7"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"q1.top()="<<q1.top()<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前優(yōu)先級隊列中的元素：5"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"q1.top()="<<q1.top()<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前優(yōu)先級隊列是空的"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"隊列為空時不允許使用q1.top()查看隊首元素"<<endl;
cout<<endl<<endl;
priority_queue<int,vector<int>,greater<int>> q2; //定義一個小頂堆的優(yōu)先級隊列q2，即隊首元素總是最小值
cout<<"定義小頂堆q2: priority_queue<int,vector<int>,greater<int>> q2"<<endl;
q2.push(10);//添加一個元素10
q2.push(5);//添加一個元素5
q2.push(7);//添加一個元素7
cout<<"按順序插入10、5、7這三個數(shù)據(jù)，目前優(yōu)先級隊列中的元素：10 5 7"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;//查看目前隊列中元素個數(shù)
cout<<"q2.empty()="<<q2.empty()<<endl;//查看目前隊列是否為空，1即為空，0即非空
cout<<"q2.top()="<<q2.top()<<endl;//查看目前隊列首部元素
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前優(yōu)先級隊列中的元素：10 7"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"q2.top()="<<q2.top()<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前優(yōu)先級隊列中的元素：10"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"q2.top()="<<q2.top()<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前優(yōu)先級隊列是空的"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"隊列為空時不允許使用q1.top()查看隊首元素"<<endl;
}運行結果：
定義默認大頂堆q1: priority_queue<int> q1
按順序插入10、5、7這三個數(shù)據(jù)，目前優(yōu)先級隊列中的元素：10 5 7
q1.size()=3
q1.empty()=0
q1.top()=10q1.pop()后，目前優(yōu)先級隊列中的元素：5 7
q1.size()=2
q1.empty()=0
q1.top()=7q1.pop()后，目前優(yōu)先級隊列中的元素：5
q1.size()=1
q1.empty()=0
q1.top()=5q1.pop()后，目前優(yōu)先級隊列是空的
q1.size()=0
q1.empty()=1
隊列為空時不允許使用q1.top()查看隊首元素定義小頂堆q2: priority_queue<int,vector<int>,greater<int>> q2
按順序插入10、5、7這三個數(shù)據(jù)，目前優(yōu)先級隊列中的元素：10 5 7
q2.size()=3
q2.empty()=0
q2.top()=5q2.pop()后，目前優(yōu)先級隊列中的元素：10 7
q2.size()=2
q2.empty()=0
q2.top()=7q2.pop()后，目前優(yōu)先級隊列中的元素：10
q2.size()=1
q2.empty()=0
q2.top()=10q2.pop()后，目前優(yōu)先級隊列是空的
q2.size()=0
q2.empty()=1
隊列為空時不允許使用q1.top()查看隊首元素
結構體類型的使用方法
方法一、函數(shù)里重載運算符
由于結構體默認是沒有比較大小的功能的，所以也就不能直接使用優(yōu)先級隊列，需要重載運行符大于號和小于號，然后使用less<>和greater<>切換大小頂堆
示例代碼：
#include<iostream>//c++標準頭文件，可以使用cout,cin等標準庫函數(shù)
#include<queue>//使用priority_queue時需要的頭文件
using namespace std;//命名空間，防止重名給程序帶來各種隱患，使用cin,cout,stack,map,set,vector,queue時都要使用
struct test{//定義一個結構體test
int val;
test(int v){//構造函數(shù)
this->val=v;
}
bool operator > (const test t)const{//重載運算符>
return val>t.val;
}
bool operator < (const test t)const{//重載運算符
return val<t.val;
}
};
int main(){
priority_queue<test,vector<test>,less<test>> q1;//定義一個大頂堆q1
cout<<"定義一個大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl;
q1.push(test(10));//向隊列中添加一個test，val的值為10
q1.push(test(5));//向隊列中添加一個test，val的值為5
q1.push(test(7));//向隊列中添加一個test，val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊列的元素：test(10) test(5) test(7)" <<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前隊列的元素：test(5) test(7)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前隊列的元素：test(5)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前隊列是空的"<<endl;
cout<<"目前隊列是空的，不能使用q1.top()查詢隊首元素"<<endl;
cout<<endl<<endl;
priority_queue<test,vector<test>,greater<test>> q2;//定義一個大頂堆q1
cout<<"定義一個小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl;
q2.push(test(10));//向隊列中添加一個test，val的值為10
q2.push(test(5));//向隊列中添加一個test，val的值為5
q2.push(test(7));//向隊列中添加一個test，val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊列的元素：test(10) test(5) test(7)" <<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前隊列的元素：test(10) test(7)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前隊列的元素：test(10)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q1.pop()后，目前隊列是空的"<<endl;
cout<<"目前隊列是空的，不能使用q2.top()查詢隊首元素"<<endl;
}運行結果：
#include<iostream>//c++標準頭文件，可以使用cout,cin等標準庫函數(shù)
#include<queue>//使用priority_queue時需要的頭文件
using namespace std;//命名空間，防止重名給程序帶來各種隱患，使用cin,cout,stack,map,set,vector,queue時都要使用
struct test{//定義一個結構體test
int val;
test(int v){//構造函數(shù)
this->val=v;
}
bool operator > (const test t)const{//重載運算符>
return val>t.val;
}
bool operator < (const test t)const{//重載運算符
return val<t.val;
}
};
int main(){
priority_queue<test,vector<test>,less<test>> q1;//定義一個大頂堆q1
cout<<"定義一個大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl;
q1.push(test(10));//向隊列中添加一個test，val的值為10
q1.push(test(5));//向隊列中添加一個test，val的值為5
q1.push(test(7));//向隊列中添加一個test，val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊列的元素：test(10) test(5) test(7)" <<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前隊列的元素：test(5) test(7)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前隊列的元素：test(5)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后，目前隊列是空的"<<endl;
cout<<"目前隊列是空的，不能使用q1.top()查詢隊首元素"<<endl;
cout<<endl<<endl;
priority_queue<test,vector<test>,greater<test>> q2;//定義一個大頂堆q1
cout<<"定義一個小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl;
q2.push(test(10));//向隊列中添加一個test，val的值為10
q2.push(test(5));//向隊列中添加一個test，val的值為5
q2.push(test(7));//向隊列中添加一個test，val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊列的元素：test(10) test(5) test(7)" <<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前隊列的元素：test(10) test(7)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后，目前隊列的元素：test(10)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q1.pop()后，目前隊列是空的"<<endl;
cout<<"目前隊列是空的，不能使用q2.top()查詢隊首元素"<<endl;
}方法二、自定義結構體重載括號運算符
很多時候，我們不應該重載結構體的運算符。像數(shù)據(jù)結構vector，它有它的基本運算方法，我們不應該重載它的運算符。
此時，我們就應該自定義結構體替代less<>和greater<>,通過重載括號符就可以更改比較規(guī)則
示例代碼：
#include<iostream>//c++標準頭文件，可以使用cout,cin等標準庫函數(shù)
#include<queue>//使用priority_queue時需要的頭文件
using namespace std;//命名空間，防止重名給程序帶來各種隱患，使用cin,cout,stack,map,set,vector,queue時都要使用
struct test{//定義一個結構體test
int val;
test(int v){//構造函數(shù)
this->val=v;
}
// 下面是基本的運算方法，我們不能隨意更改它
bool operator > (const test t)const{//重載運算符
return val>t.val;
}
bool operator < (const test t)const{//重載運算符
return val<t.val;
}
};
struct cmp{
bool operator () (const test t1,const test t2)const{//重載括號運算符
return t1.val<t2.val;//小于號是大根堆，大于號是小根堆
}
};
int main(){
priority_queue<test,vector<test>,cmp> q;//自定義一個優(yōu)先級隊列q
cout<<"自定義一個優(yōu)先級隊列q: priority_queue<test,vector<test>,cmp> q"<<endl;
q.push(test(10));//向隊列中添加一個test，val的值為10
q.push(test(5));//向隊列中添加一個test，val的值為5
q.push(test(7));//向隊列中添加一個test，val的值為7
cout<<"q.top().val="<<q.top().val<<endl;
cout<<endl;
q.pop();
cout<<"q.top().val="<<q.top().val<<endl;
cout<<endl;
q.pop();
cout<<"q.top().val="<<q.top().val<<endl;
cout<<endl;
q.pop();
cout<<"目前隊列是空的，不能使用q.top()查詢隊首元素"<<endl;
}運行結果：
自定義一個優(yōu)先級隊列q: priority_queue<test,vector<test>,cmp> q
q.top().val=10q.top().val=7
q.top().val=5
目前隊列是空的，不能使用q.top()查詢隊首元素
把括號運算符里的小于號改為大于號就是小頂堆了
自定義一個優(yōu)先級隊列q: priority_queue<test,vector<test>,cmp> q
q.top().val=5q.top().val=7
q.top().val=10
目前隊列是空的，不能使用q.top()查詢隊首元素
至此，優(yōu)先級隊列的基本用法就學完啦
是不是很簡單呢？
剛接觸肯定會覺得難，多些做題多些用，熟悉了就容易了，兄弟萌，加油?。。?/p>
到此這篇關于c++ priority_queue用法 入門超詳細教程的文章就介紹到這了,更多相關c++ priority_queue用法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了在iOS中給視頻添加濾鏡的方法示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-03-03
和一維數(shù)組類似，C++?將二維數(shù)組名解釋為其第一個元素的地址，而二維數(shù)組的第一個元素為一維數(shù)組，下面詳細總結下二維數(shù)組名的性質,需要的朋友可以參考下2022-09-09
這篇文章主要給大家介紹了關于C++實現(xiàn)線程池的簡單方法，文中通過示例代碼介紹的非常詳細，對大家學習或者使用C++具有一定的參考學習價值，需要的朋友們下面來一起學習學習吧2020-05-05
C++數(shù)組模擬之單鏈表與雙鏈表和棧和隊列的實現(xiàn)過程
這篇文章主要介紹了C++數(shù)組模擬之單鏈表與雙鏈表和棧和隊列的實現(xiàn)過程，了解內部原理是為了幫助我們做擴展，同時也是驗證了一個人的學習能力，如果你想讓自己的職業(yè)道路更上一層樓，這些底層的東西你是必須要會的，跟隨下文來具體了解吧2023-02-02
大家好，本篇文章主要講的是C++實現(xiàn)轉置矩陣的循環(huán)，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
本文主要介紹了C++封裝成DLL并調用的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
這篇文章主要介紹了C/C++中的typedef和#define詳解的相關資料,需要的朋友可以參考下2017-02-02
本篇文章對string與char*的轉換進行的介紹。需要的朋友參考下2013-05-05
這篇文章主要給大家介紹了關于Qt兩種定時器使用實現(xiàn)方式的相關資料,Qt中的定時器類是QTimer,QTimer不是一個可見的界面組件,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-01-01
這篇文章主要為大家介紹了C語言的指針，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01