優(yōu)先隊(duì)列的定義
百度百科定義
優(yōu)先隊(duì)列是0個(gè)或多個(gè)元素的集合,每個(gè)元素都有一個(gè)優(yōu)先權(quán)或值,對優(yōu)先隊(duì)列執(zhí)行的操作有1) 查找;2) 插入一個(gè)新元素;3) 刪除.在最小優(yōu)先隊(duì)列(min priority queue)中,查找操作用來搜索優(yōu)先權(quán)最小的元素,刪除操作用來刪除該元素;對于最大優(yōu)先隊(duì)列(max priority queue),查找操作用來搜索優(yōu)先權(quán)最大的元素,刪除操作用來刪除該元素.優(yōu)先權(quán)隊(duì)列中的元素可以有相同的優(yōu)先權(quán),查找與刪除操作可根據(jù)任意優(yōu)先權(quán)進(jìn)行.
簡化一點(diǎn)來說：
優(yōu)先隊(duì)列是一種比較重要的數(shù)據(jù)結(jié)構(gòu)，它是有二項(xiàng)隊(duì)列編寫而成的，可以以O(shè)(log n) 的效率查找一個(gè)隊(duì)列中的最大值或者最小值，其中是最大值還是最小值是根據(jù)創(chuàng)建的優(yōu)先隊(duì)列的性質(zhì)來決定的。
priority_queue
其實(shí)priority_queue就是一個(gè)stl的容器。
模板參數(shù)?
優(yōu)先隊(duì)列有三個(gè)參數(shù)，其聲明形式為：
priority_queue< type, container, function > 名稱后兩個(gè)是可以省略的，就是按照默認(rèn)（降序）來的，第一個(gè)必須寫。
其中：
- type：數(shù)據(jù)類型；
- container：實(shí)現(xiàn)優(yōu)先隊(duì)列的底層容器；
- function：元素之間的比較方式；
對于container，要求必須是數(shù)組形式實(shí)現(xiàn)的容器
在STL中，默認(rèn)情況下（不加后面兩個(gè)參數(shù)）是以vector為容器，以 operator< 為比較方式，所以在只使用第一個(gè)參數(shù)時(shí)，優(yōu)先隊(duì)列默認(rèn)是一個(gè)最大堆，每次輸出的堆頂元素是此時(shí)堆中的最大元素。
priority_queue成員函數(shù)
假設(shè)type類型為int，則：
假設(shè)type類型為int，則：
bool empty() const
返回值為true，說明隊(duì)列為空；
int size() const
返回優(yōu)先隊(duì)列中元素的數(shù)量；
void pop()
刪除隊(duì)列頂部的元素，也即根節(jié)點(diǎn)
int top()
返回隊(duì)列中的頂部元素，但不刪除該元素；
void push(int arg)
將元素arg插入到隊(duì)列之中；
大頂堆與小頂堆
大頂堆（降序）
//構(gòu)造一個(gè)空的優(yōu)先隊(duì)列（此優(yōu)先隊(duì)列默認(rèn)為大頂堆）
priority_queue<int> big_heap;
//另一種構(gòu)建大頂堆的方法
priority_queue<int,vector<int>,less<int> > big_heap2;
小頂堆（升序）
//構(gòu)造一個(gè)空的優(yōu)先隊(duì)列,此優(yōu)先隊(duì)列是一個(gè)小頂堆
priority_queue<int,vector<int>,greater<int> > small_heap;
注意事項(xiàng)
需要注意的是，如果使用less和greater，需要頭文件：文章來源：http://www.zghlxwxcb.cn/news/detail-705169.html
#include <functional>
代碼案例
#include <bits/stdc++.h>
using namespace std;
int main()
{
//對于基礎(chǔ)類型 默認(rèn)是大頂堆
priority_queue<int> a;
//等同于 priority_queue<int, vector<int>, less<int> > a;
// 這樣就是小頂堆
// 好習(xí)慣 >>中間要加空格
priority_queue<int, vector<int>, greater<int> > c;
priority_queue<string> b;
for (int i = 0; i < 5; i++)
{
a.push(i);
c.push(i);
}
// 降序輸出
while (!a.empty())
{
cout << a.top() << ' ';
a.pop();
}
cout << endl;
// 升序輸出
while (!c.empty())
{
cout << c.top() << ' ';
c.pop();
}
cout << endl;
b.push("abc");
b.push("abcd");
b.push("cbd");
while (!b.empty())
{
cout << b.top() << ' ';
b.pop();
}
cout << endl;
return 0;
}
請您點(diǎn)贊，關(guān)注加收藏，謝謝您的閱讀！文章來源地址http://www.zghlxwxcb.cn/news/detail-705169.html
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——優(yōu)先隊(duì)列c++詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
