priority_queue 基本介紹
priority_queue 是 STL queue 中一部分。普通的隊列是一種先進先出的資料結構，元素在隊列尾追加，而從隊列頭删除。在優先隊列中，元素被賦予優先級。當通路元素時，具有最高優先級的元素最先删除。優先隊列具有最進階先出 （first in, largest out）的行為特征。
priority_queue 和 queue 不同的就在于我們可以自定義其中資料的優先級, 讓優先級高的排在隊列前面,優先出隊。
優先隊列具有隊列的所有特性，包括隊列的基本操作，隻是在這基礎上添加了内部的一個排序，它本質是一個堆實作的。
頭檔案
和 queue 一樣，需要包含 #include <queue>。
同時，priority_queue 也是屬于标準命名空間，即 using namespace std。
定義方法
priority_queue<Type, Container, Functional> 變量名;
1、Type 就是資料類型。
2、Container 就是容器類型（Container 必須是用數組實作的容器，比如 vector,deque 等等，但不能用 list。STL裡面預設用的是vector）。
3、Functional 就是比較的方式。
//升序隊列，小頂堆
priority_queue <int, vector<int>, greater<int> > q;
//降序隊列，大頂堆
priority_queue <int, vector<int>, less<int> > q;
//greater和less是std實作的兩個仿函數（就是使一個類的使用看上去像一個函數。其實作就是類中實作一個operator()，這個類就有了類似函數的行為，就是一個仿函數類了）
基本操作
priority_queue 的基本操作類似 STL stack。
加入資料
使用 push() 函數。
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main () {
std::priority_queue<int> mypq;
mypq.push(30); //隊列資料: 30
mypq.push(100); //隊列資料: 100 30
mypq.push(25); //隊列資料: 100 30 25
mypq.push(40); //隊列資料: 100 40 30 25
return 0;
}
擷取頂部資料
使用 top() 函數。
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main () {
std::priority_queue<int> mypq;
mypq.push(30); //隊列資料: 30
std::cout << mypq.top() << std::endl; //30
mypq.push(100); //隊列資料: 100 30
std::cout << mypq.top() << std::endl; //100
mypq.push(25); //隊列資料: 100 30 25
std::cout << mypq.top() << std::endl; //100
mypq.push(40); //隊列資料: 100 40 30 25
std::cout << mypq.top() << std::endl; //100
return 0;
}
删除資料
使用 pop() 函數，隻能删除頂部元素。
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main () {
std::priority_queue<int> mypq;
mypq.push(30); //隊列資料: 30
std::cout << mypq.top() << std::endl; //30
mypq.push(100); //隊列資料: 100 30
std::cout << mypq.top() << std::endl; //100
mypq.pop(); //隊列資料: 30
mypq.push(25); //隊列資料: 30 25
std::cout << mypq.top() << std::endl; //30
mypq.push(40); //隊列資料: 40 30 25
std::cout << mypq.top() << std::endl; //40
return 0;
}
隊列中資料大小
使用 size() 函數。
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main () {
std::priority_queue<int> mypq;
mypq.push(30); //隊列資料: 30
std::cout << mypq.size() << std::endl; //1
mypq.push(100); //隊列資料: 100 30
std::cout << mypq.size() << std::endl; //2
mypq.push(25); //隊列資料: 100 30 25
std::cout << mypq.size() << std::endl; //3
mypq.push(40); //隊列資料: 100 40 30 25
std::cout << mypq.size() << std::endl; //4
return 0;
}
隊列是否為空
使用 empty() 函數判斷。
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main () {
std::priority_queue<int> mypq;
mypq.push(30); //隊列資料: 30
mypq.push(100); //隊列資料: 100 30
mypq.push(25); //隊列資料: 100 30 25
mypq.push(40); //隊列資料: 100 40 30 25
int sum=0;
while (!mypq.empty()) {
sum += mypq.top();
mypq.pop();
}//sum最終結果為100+40+30+25
return 0;
}
例子
C++ 内置資料類型
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
//對于基礎類型 預設是大頂堆
priority_queue<int> big;
//等同于 priority_queue<int, vector<int>, less<int> > big;
//這裡一定要有空格，不然成了右移運算符↓↓
priority_queue<int, vector<int>, greater<int> > small; //這樣就是小頂堆
priority_queue<string> b;
for (int i = 0; i < 10; i++) {
big.push(i);
small.push(i);
}
while (!big.empty()) {
cout << big.top() << ' ';
big.pop();
}
cout << endl;
while (!small.empty()) {
cout << small.top() << ' ';
small.pop();
}
cout << endl;
b.push("abc");
b.push("abcd");
b.push("cbd");
while (!b.empty()) {
cout << b.top() << ' ';
b.pop();
}
cout << endl;
return 0;
}
運作結果如下圖。
pair 做為資料
比較規則為： 先比較 pair 第一個元素，第一個相等比較第二個。
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
int main() {
priority_queue<pair<int, int> > a;
pair<int, int> b(1, 2);
pair<int, int> c(1, 3);
pair<int, int> d(2, 5);
a.push(d);
a.push(c);
a.push(b);
while (!a.empty()) {
cout << a.top().first << ' ' << a.top().second << '\n';
a.pop();
}
return 0;
}
運作結果如下圖所示。
自定義資料類型
#include <iostream>
#include <queue>
using namespace std;
//方法1
typedef struct _st1 {
int x;
_st1(int a) {x = a;}
bool operator<(const _st1& a) const {
//運算符重載<
return x < a.x; //大頂堆
}
} ST1;
//方法2
typedef struct _st2 {
//重寫仿函數
bool operator() (_st1 a, _st1 b) {
return a.x < b.x; //大頂堆
}
} ST2;
int main()
{
ST1 a(6);
ST1 b(2);
ST1 c(13);
priority_queue<ST1> d;
d.push(b);
d.push(c);
d.push(a);
while (!d.empty()) {
cout << d.top().x << endl;
d.pop();
}
cout << endl;
priority_queue<ST1, vector<ST1>, ST2> f;
f.push(b);
f.push(c);
f.push(a);
while (!f.empty()) {
cout << f.top().x << endl;
f.pop();
}
return 0;
}
運作結果如下圖所示。