c++ priority_queue用法入門超詳細(xì)教程
1、priority_queue的作用
priority_queue即優(yōu)先級(jí)隊(duì)列,它的使用場(chǎng)景很多,它底層是用大小根堆實(shí)現(xiàn)的,可以用log(n)的時(shí)間動(dòng)態(tài)地維護(hù)數(shù)據(jù)的有序性。適用于許多場(chǎng)景,比如簡(jiǎn)化哈夫曼樹算法、dijkstra算法等等
priority_queue是不允許隨機(jī)訪問(wèn),只能訪問(wèn)隊(duì)列首部的元素,也只能對(duì)首部元素進(jìn)行出隊(duì),下面進(jìn)行學(xué)習(xí)它的基本用法
2、priority_queue的定義
頭文件
#include<queue>
基本定義方法:
基本定義默認(rèn)是使用大頂堆的,即隊(duì)首總是最大的元素
priority_queue<儲(chǔ)存的類型> 容器名
如:
priority_queue<int> q;//儲(chǔ)存int型數(shù)據(jù) priority_queue<double> q;//儲(chǔ)存double型數(shù)據(jù) priority_queue<string> q;//儲(chǔ)存string型數(shù)據(jù) priority_queue<結(jié)構(gòu)體名> q;//儲(chǔ)存結(jié)構(gòu)體或者類
快速切換大小頂堆定義:
less<儲(chǔ)存的數(shù)據(jù)類型> 即使用大頂堆
greater<儲(chǔ)存的數(shù)據(jù)類型> 即是用小頂堆
priority_queue<儲(chǔ)存的類型,vector<儲(chǔ)存的類型>,頂堆的類型> 容器名
如:
使用大頂堆的隊(duì)列:
priority_queue<int,vector<int>,less<int>> q;//儲(chǔ)存int型數(shù)據(jù) priority_queue<double,vector<double>,less<double>> q;//儲(chǔ)存double型數(shù)據(jù) priority_queue<string,vector<string>,less<string>> q;//儲(chǔ)存string型數(shù)據(jù) priority_queue<結(jié)構(gòu)體名,vector<結(jié)構(gòu)體名>,less<結(jié)構(gòu)體名>> q;//儲(chǔ)存結(jié)構(gòu)體或者類
使用小頂堆的隊(duì)列:
priority_queue<int,vector<int>,greater<int>> q;//儲(chǔ)存int型數(shù)據(jù) priority_queue<double,vector<double>,greater<double>> q;//儲(chǔ)存double型數(shù)據(jù) priority_queue<string,vector<string>,greater<string>> q;//儲(chǔ)存string型數(shù)據(jù) priority_queue<結(jié)構(gòu)體名,vector<結(jié)構(gòu)體名>,greater<結(jié)構(gòu)體名>> q;//儲(chǔ)存結(jié)構(gòu)體或者類
使用結(jié)構(gòu)體重載運(yùn)算符定義:
新建一個(gè)結(jié)構(gòu)體,通過(guò)重載運(yùn)算符改變頂堆的排序,這里是拓展用法,也是必學(xué)用法,因?yàn)樽约簩懙慕Y(jié)構(gòu)體是沒有比較大小功能的,當(dāng)然也可以在原本的結(jié)構(gòu)體里面重載運(yùn)算符
priority_queue<int,vector<int>,cmp> q;//儲(chǔ)存int型數(shù)據(jù) priority_queue<double,vector<double>,cmp> q;//儲(chǔ)存double型數(shù)據(jù) priority_queue<string,vector<string>,cmp> q;//儲(chǔ)存string型數(shù)據(jù) priority_queue<結(jié)構(gòu)體名,vector<結(jié)構(gòu)體名>,cmp> q;//儲(chǔ)存結(jié)構(gòu)體或者類
3、priority_queue的成員函數(shù)
empty() 如果優(yōu)先隊(duì)列為空,則返回真 pop() 刪除第一個(gè)元素 push() 加入一個(gè)元素 size() 返回優(yōu)先隊(duì)列中擁有的元素的個(gè)數(shù) top() 返回優(yōu)先隊(duì)列中有最高優(yōu)先級(jí)的元素
4、priority_queue的基本用法
普通數(shù)據(jù)類型的使用方法:
示例代碼:
#include<iostream>//c++標(biāo)準(zhǔn)頭文件,可以使用cout,cin等標(biāo)準(zhǔn)庫(kù)函數(shù)
#include<queue>//使用priority_queue時(shí)需要的頭文件
using namespace std;//命名空間,防止重名給程序帶來(lái)各種隱患,使用cin,cout,stack,map,set,vector,queue時(shí)都要使用
int main(){
priority_queue<int> q1;//定義一個(gè)默認(rèn)大頂堆的優(yōu)先級(jí)隊(duì)列q1,即隊(duì)首元素總是最大值
// priority_queue<int,vector<int>,less<int>> q1; //這樣顯示定義大頂堆也是可以的
cout<<"定義默認(rèn)大頂堆q1: priority_queue<int> q1"<<endl;
q1.push(10);//添加一個(gè)元素10
q1.push(5);//添加一個(gè)元素5
q1.push(7);//添加一個(gè)元素7
cout<<"按順序插入10、5、7這三個(gè)數(shù)據(jù),目前優(yōu)先級(jí)隊(duì)列中的元素:10 5 7"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;//查看目前隊(duì)列中元素個(gè)數(shù)
cout<<"q1.empty()="<<q1.empty()<<endl;//查看目前隊(duì)列是否為空,1即為空,0即非空
cout<<"q1.top()="<<q1.top()<<endl;//查看目前隊(duì)列首部元素
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前優(yōu)先級(jí)隊(duì)列中的元素: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)先級(jí)隊(duì)列中的元素: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)先級(jí)隊(duì)列是空的"<<endl;
cout<<"q1.size()="<<q1.size()<<endl;
cout<<"q1.empty()="<<q1.empty()<<endl;
cout<<"隊(duì)列為空時(shí)不允許使用q1.top()查看隊(duì)首元素"<<endl;
cout<<endl<<endl;
priority_queue<int,vector<int>,greater<int>> q2; //定義一個(gè)小頂堆的優(yōu)先級(jí)隊(duì)列q2,即隊(duì)首元素總是最小值
cout<<"定義小頂堆q2: priority_queue<int,vector<int>,greater<int>> q2"<<endl;
q2.push(10);//添加一個(gè)元素10
q2.push(5);//添加一個(gè)元素5
q2.push(7);//添加一個(gè)元素7
cout<<"按順序插入10、5、7這三個(gè)數(shù)據(jù),目前優(yōu)先級(jí)隊(duì)列中的元素:10 5 7"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;//查看目前隊(duì)列中元素個(gè)數(shù)
cout<<"q2.empty()="<<q2.empty()<<endl;//查看目前隊(duì)列是否為空,1即為空,0即非空
cout<<"q2.top()="<<q2.top()<<endl;//查看目前隊(duì)列首部元素
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前優(yōu)先級(jí)隊(duì)列中的元素: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)先級(jí)隊(duì)列中的元素: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)先級(jí)隊(duì)列是空的"<<endl;
cout<<"q2.size()="<<q2.size()<<endl;
cout<<"q2.empty()="<<q2.empty()<<endl;
cout<<"隊(duì)列為空時(shí)不允許使用q1.top()查看隊(duì)首元素"<<endl;
}運(yùn)行結(jié)果:
定義默認(rèn)大頂堆q1: priority_queue<int> q1
按順序插入10、5、7這三個(gè)數(shù)據(jù),目前優(yōu)先級(jí)隊(duì)列中的元素:10 5 7
q1.size()=3
q1.empty()=0
q1.top()=10q1.pop()后,目前優(yōu)先級(jí)隊(duì)列中的元素:5 7
q1.size()=2
q1.empty()=0
q1.top()=7q1.pop()后,目前優(yōu)先級(jí)隊(duì)列中的元素:5
q1.size()=1
q1.empty()=0
q1.top()=5q1.pop()后,目前優(yōu)先級(jí)隊(duì)列是空的
q1.size()=0
q1.empty()=1
隊(duì)列為空時(shí)不允許使用q1.top()查看隊(duì)首元素定義小頂堆q2: priority_queue<int,vector<int>,greater<int>> q2
按順序插入10、5、7這三個(gè)數(shù)據(jù),目前優(yōu)先級(jí)隊(duì)列中的元素:10 5 7
q2.size()=3
q2.empty()=0
q2.top()=5q2.pop()后,目前優(yōu)先級(jí)隊(duì)列中的元素:10 7
q2.size()=2
q2.empty()=0
q2.top()=7q2.pop()后,目前優(yōu)先級(jí)隊(duì)列中的元素:10
q2.size()=1
q2.empty()=0
q2.top()=10q2.pop()后,目前優(yōu)先級(jí)隊(duì)列是空的
q2.size()=0
q2.empty()=1
隊(duì)列為空時(shí)不允許使用q1.top()查看隊(duì)首元素
結(jié)構(gòu)體類型的使用方法
方法一、函數(shù)里重載運(yùn)算符
由于結(jié)構(gòu)體默認(rèn)是沒有比較大小的功能的,所以也就不能直接使用優(yōu)先級(jí)隊(duì)列,需要重載運(yùn)行符大于號(hào)和小于號(hào),然后使用less<>和greater<>切換大小頂堆
示例代碼:
#include<iostream>//c++標(biāo)準(zhǔn)頭文件,可以使用cout,cin等標(biāo)準(zhǔn)庫(kù)函數(shù)
#include<queue>//使用priority_queue時(shí)需要的頭文件
using namespace std;//命名空間,防止重名給程序帶來(lái)各種隱患,使用cin,cout,stack,map,set,vector,queue時(shí)都要使用
struct test{//定義一個(gè)結(jié)構(gòu)體test
int val;
test(int v){//構(gòu)造函數(shù)
this->val=v;
}
bool operator > (const test t)const{//重載運(yùn)算符>
return val>t.val;
}
bool operator < (const test t)const{//重載運(yùn)算符
return val<t.val;
}
};
int main(){
priority_queue<test,vector<test>,less<test>> q1;//定義一個(gè)大頂堆q1
cout<<"定義一個(gè)大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl;
q1.push(test(10));//向隊(duì)列中添加一個(gè)test,val的值為10
q1.push(test(5));//向隊(duì)列中添加一個(gè)test,val的值為5
q1.push(test(7));//向隊(duì)列中添加一個(gè)test,val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊(duì)列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前隊(duì)列的元素:test(5) test(7)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前隊(duì)列的元素:test(5)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前隊(duì)列是空的"<<endl;
cout<<"目前隊(duì)列是空的,不能使用q1.top()查詢隊(duì)首元素"<<endl;
cout<<endl<<endl;
priority_queue<test,vector<test>,greater<test>> q2;//定義一個(gè)大頂堆q1
cout<<"定義一個(gè)小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl;
q2.push(test(10));//向隊(duì)列中添加一個(gè)test,val的值為10
q2.push(test(5));//向隊(duì)列中添加一個(gè)test,val的值為5
q2.push(test(7));//向隊(duì)列中添加一個(gè)test,val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊(duì)列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前隊(duì)列的元素:test(10) test(7)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前隊(duì)列的元素:test(10)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q1.pop()后,目前隊(duì)列是空的"<<endl;
cout<<"目前隊(duì)列是空的,不能使用q2.top()查詢隊(duì)首元素"<<endl;
}運(yùn)行結(jié)果:
#include<iostream>//c++標(biāo)準(zhǔn)頭文件,可以使用cout,cin等標(biāo)準(zhǔn)庫(kù)函數(shù)
#include<queue>//使用priority_queue時(shí)需要的頭文件
using namespace std;//命名空間,防止重名給程序帶來(lái)各種隱患,使用cin,cout,stack,map,set,vector,queue時(shí)都要使用
struct test{//定義一個(gè)結(jié)構(gòu)體test
int val;
test(int v){//構(gòu)造函數(shù)
this->val=v;
}
bool operator > (const test t)const{//重載運(yùn)算符>
return val>t.val;
}
bool operator < (const test t)const{//重載運(yùn)算符
return val<t.val;
}
};
int main(){
priority_queue<test,vector<test>,less<test>> q1;//定義一個(gè)大頂堆q1
cout<<"定義一個(gè)大根堆q1: priority_queue<test,vector<test>,less<test>> q1"<<endl;
q1.push(test(10));//向隊(duì)列中添加一個(gè)test,val的值為10
q1.push(test(5));//向隊(duì)列中添加一個(gè)test,val的值為5
q1.push(test(7));//向隊(duì)列中添加一個(gè)test,val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊(duì)列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前隊(duì)列的元素:test(5) test(7)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前隊(duì)列的元素:test(5)"<<endl;
cout<<"q1.top().val="<<q1.top().val<<endl;
cout<<endl;
q1.pop();
cout<<"q1.pop()后,目前隊(duì)列是空的"<<endl;
cout<<"目前隊(duì)列是空的,不能使用q1.top()查詢隊(duì)首元素"<<endl;
cout<<endl<<endl;
priority_queue<test,vector<test>,greater<test>> q2;//定義一個(gè)大頂堆q1
cout<<"定義一個(gè)小根堆q2: priority_queue<test,vector<test>,greate<test>> q2"<<endl;
q2.push(test(10));//向隊(duì)列中添加一個(gè)test,val的值為10
q2.push(test(5));//向隊(duì)列中添加一個(gè)test,val的值為5
q2.push(test(7));//向隊(duì)列中添加一個(gè)test,val的值為7
cout<<"按順序添加val的值為10、5、7的test,目前隊(duì)列的元素:test(10) test(5) test(7)" <<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前隊(duì)列的元素:test(10) test(7)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q2.pop()后,目前隊(duì)列的元素:test(10)"<<endl;
cout<<"q2.top().val="<<q2.top().val<<endl;
cout<<endl;
q2.pop();
cout<<"q1.pop()后,目前隊(duì)列是空的"<<endl;
cout<<"目前隊(duì)列是空的,不能使用q2.top()查詢隊(duì)首元素"<<endl;
}方法二、自定義結(jié)構(gòu)體重載括號(hào)運(yùn)算符
很多時(shí)候,我們不應(yīng)該重載結(jié)構(gòu)體的運(yùn)算符。像數(shù)據(jù)結(jié)構(gòu)vector,它有它的基本運(yùn)算方法,我們不應(yīng)該重載它的運(yùn)算符。
此時(shí),我們就應(yīng)該自定義結(jié)構(gòu)體替代less<>和greater<>,通過(guò)重載括號(hào)符就可以更改比較規(guī)則
示例代碼:
#include<iostream>//c++標(biāo)準(zhǔn)頭文件,可以使用cout,cin等標(biāo)準(zhǔn)庫(kù)函數(shù)
#include<queue>//使用priority_queue時(shí)需要的頭文件
using namespace std;//命名空間,防止重名給程序帶來(lái)各種隱患,使用cin,cout,stack,map,set,vector,queue時(shí)都要使用
struct test{//定義一個(gè)結(jié)構(gòu)體test
int val;
test(int v){//構(gòu)造函數(shù)
this->val=v;
}
// 下面是基本的運(yùn)算方法,我們不能隨意更改它
bool operator > (const test t)const{//重載運(yùn)算符
return val>t.val;
}
bool operator < (const test t)const{//重載運(yùn)算符
return val<t.val;
}
};
struct cmp{
bool operator () (const test t1,const test t2)const{//重載括號(hào)運(yùn)算符
return t1.val<t2.val;//小于號(hào)是大根堆,大于號(hào)是小根堆
}
};
int main(){
priority_queue<test,vector<test>,cmp> q;//自定義一個(gè)優(yōu)先級(jí)隊(duì)列q
cout<<"自定義一個(gè)優(yōu)先級(jí)隊(duì)列q: priority_queue<test,vector<test>,cmp> q"<<endl;
q.push(test(10));//向隊(duì)列中添加一個(gè)test,val的值為10
q.push(test(5));//向隊(duì)列中添加一個(gè)test,val的值為5
q.push(test(7));//向隊(duì)列中添加一個(gè)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<<"目前隊(duì)列是空的,不能使用q.top()查詢隊(duì)首元素"<<endl;
}運(yùn)行結(jié)果:
自定義一個(gè)優(yōu)先級(jí)隊(duì)列q: priority_queue<test,vector<test>,cmp> q
q.top().val=10q.top().val=7
q.top().val=5
目前隊(duì)列是空的,不能使用q.top()查詢隊(duì)首元素
把括號(hào)運(yùn)算符里的小于號(hào)改為大于號(hào)就是小頂堆了
自定義一個(gè)優(yōu)先級(jí)隊(duì)列q: priority_queue<test,vector<test>,cmp> q
q.top().val=5q.top().val=7
q.top().val=10
目前隊(duì)列是空的,不能使用q.top()查詢隊(duì)首元素
至此,優(yōu)先級(jí)隊(duì)列的基本用法就學(xué)完啦
是不是很簡(jiǎn)單呢?
剛接觸肯定會(huì)覺得難,多些做題多些用,熟悉了就容易了,兄弟萌,加油?。?!
到此這篇關(guān)于c++ priority_queue用法 入門超詳細(xì)教程的文章就介紹到這了,更多相關(guān)c++ priority_queue用法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- C++ 中"priority_queue" 優(yōu)先級(jí)隊(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++ 容器適配器priority_queue的使用及實(shí)現(xiàn)代碼
- 詳解c++優(yōu)先隊(duì)列priority_queue的用法
- 詳解C++模擬實(shí)現(xiàn)priority_queue(仿函數(shù))
- C++深入刨析優(yōu)先級(jí)隊(duì)列priority_queue的使用
- C++中priority_queue的實(shí)現(xiàn)
相關(guān)文章
輸入3個(gè)字符串,將它們按照字母由大到小排序(示例代碼)
我們可以用string方法定義字符串變量。以下是具體實(shí)現(xiàn)代碼。需要的朋友可以過(guò)來(lái)參考下,希望對(duì)大家有所幫助2013-10-10
C語(yǔ)言關(guān)于二叉樹中堆的創(chuàng)建和使用整理
大家好,這里是針對(duì)二叉樹中堆結(jié)構(gòu)的順序儲(chǔ)存,整理出來(lái)一篇博客供我們一起復(fù)習(xí)和學(xué)習(xí),如果文章中有理解不當(dāng)?shù)牡胤?還希望朋友們?cè)谠u(píng)論區(qū)指出,我們相互學(xué)習(xí),共同進(jìn)步2022-08-08
C++?LeetCode1827題解最少操作使數(shù)組遞增
這篇文章主要為大家介紹了C++?LeetCode1827題解最少操作使數(shù)組遞增示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-12-12
C語(yǔ)言對(duì)CSV文件從最后往前一行一行讀取的實(shí)現(xiàn)方法
今天小編就為大家分享一篇關(guān)于C語(yǔ)言對(duì)CSV文件從最后往前一行一行讀取的實(shí)現(xiàn)方法,小編覺得內(nèi)容挺不錯(cuò)的,現(xiàn)在分享給大家,具有很好的參考價(jià)值,需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
C語(yǔ)言實(shí)現(xiàn)學(xué)生選課系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)學(xué)生選課系統(tǒng),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-02-02
利用C語(yǔ)言實(shí)現(xiàn)猜數(shù)字游戲
這篇文章主要為大家詳細(xì)介紹了利用C語(yǔ)言實(shí)現(xiàn)猜數(shù)字游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-02-02
舉例講解C語(yǔ)言的fork()函數(shù)創(chuàng)建子進(jìn)程的用法
fork函數(shù)是Linux下一個(gè)近乎專有的C語(yǔ)言函數(shù),因?yàn)槭褂脮r(shí)需要調(diào)用unistd.h這個(gè)頭文件,這里我們就在Linux環(huán)境下舉例講解C語(yǔ)言的fork()函數(shù)創(chuàng)建子進(jìn)程的用法,需要的朋友可以參考下2016-06-06

