柚子快報(bào)邀請碼778899分享：開發(fā)語言 C++——優(yōu)先級隊(duì)列

http://yzkb.51969.com/

前言：這篇文章我們繼續(xù)來分享一個(gè)c++的容器——優(yōu)先級隊(duì)列。

一.理解優(yōu)先級

何為優(yōu)先級一說？實(shí)際上就是有順序的意思。

優(yōu)先級隊(duì)列，即有順序的隊(duì)列，是一個(gè)無需我們自己進(jìn)行排序操作，在數(shù)據(jù)傳入時(shí)就會(huì)由容器自己排好序的隊(duì)列。

先來看實(shí)例：

使用該隊(duì)列，同樣需要包含頭文件#include。

在默認(rèn)情況下，優(yōu)先級隊(duì)列是按照從大到小排序的，而在數(shù)據(jù)結(jié)構(gòu)中，也有一個(gè)能夠自主排序，沒錯(cuò)，就是堆。從大到小的順序，也就是大堆。

那么如果想要實(shí)現(xiàn)小堆，又該怎么辦呢？只需要增加一下模版參數(shù)：

至于為什么這樣寫就是小堆，我們再接下來的模擬實(shí)現(xiàn)中進(jìn)行解答。

二.基本框架

堆可以通過父節(jié)點(diǎn)或字節(jié)點(diǎn)的下標(biāo)來互相找到對方的下標(biāo)，所以一般情況都以數(shù)組為模板。?

template >

class priority_queue

{

public:

//向上調(diào)整

void adjust_up(size_t child)

{

int parent = (child - 1) / 2;

while (child > 0)

{

if (_con[child] > _con[parent])

{

swap(_con[child], _con[parent]);

child = parent;

int parent = (child - 1) / 2;

}

else

{

break;

}

}

}

//向下調(diào)整

void adjust_down(size_t parent)

{

size_t child = parent * 2 + 1;

while (child < _con.size())

{

if (child + 1 < _con.size() && _con[child + 1] > _con[child])

{

++child;

}

if (_con[child] > _con[parent])

{

swap(_con[child], _con[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

//插入

void push(const T& x)

{

_con.push_back(x);

adjust_up(_con.size() - 1);

}

//刪除

void pop()

{

swap(_con[_con.size() - 1], _con[0]);

_con.pop_back();

adjust_down(0);

}

//隊(duì)頭元素

T& top()

{

return _con[0];

}

//數(shù)據(jù)個(gè)數(shù)

size_t size()

{

return _con.size();

}

//判空

bool empty()

{

return _con.empty();

}

private:

Container _con;

};

這里我們直接給出優(yōu)先級隊(duì)列的基本常規(guī)操作，本質(zhì)就是堆的各種操作，不再一一分享。

而我們要重點(diǎn)分享的，就是如何切換升降序。

?三.仿函數(shù)

從名字就能看出，這是一個(gè)可以冒充函數(shù)的家伙，先來看例子：

template

class less

{

public:

bool operator()(const T& x, const T& y)

{

return x < y;

}

};

這段代碼不難理解，在一個(gè)類中聲明了一個(gè)運(yùn)算符重載函數(shù)，這個(gè)函數(shù)能夠進(jìn)行大小比較。?

再來看這段代碼，能夠發(fā)現(xiàn)我們能夠直接通過一個(gè)對象來進(jìn)行兩個(gè)數(shù)據(jù)之間的比較。?

這就是所謂的仿函數(shù)。?

上述仿函數(shù)是進(jìn)行“小于”比較，同樣我們也可以在創(chuàng)造一個(gè)仿函數(shù)來進(jìn)行“大于”比較。

如此一來，我們便可以通過類模板將這兩個(gè)仿函數(shù)用于排序比較。

四.實(shí)現(xiàn)可選優(yōu)先級

直接看代碼：

//小于比較

template

class less

{

public:

bool operator()(const T& x, const T& y)

{

return x < y;

}

};

//大于比較

template

class greater

{

public:

bool operator()(const T& x, const T& y)

{

return x > y;

}

};

template ,class compare = less>//注意

class priority_queue

{

//大堆

public:

//向上調(diào)整

void adjust_up(size_t child)

{

compare com;//注意

int parent = (child - 1) / 2;

while (child > 0)

{

if (com(_con[parent], _con[child]))//注意

{

swap(_con[child], _con[parent]);

child = parent;

int parent = (child - 1) / 2;

}

else

{

break;

}

}

}

//向下調(diào)整

void adjust_down(size_t parent)

{

compare com;//注意

size_t child = parent * 2 + 1;

while (child < _con.size())

{

if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))//注意

{

++child;

}

if (com(_con[parent], _con[child]))//注意

{

swap(_con[child], _con[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

其中l(wèi)ess為小于比較的類，而greater為大于比較的類。

而后我們通過使用類模板參數(shù)compare將兩者整合在一起，因?yàn)閹炖锏膬?yōu)先級隊(duì)列默認(rèn)即為大堆，所以我們使用缺省參數(shù)默認(rèn)為less。

前邊已經(jīng)提到，使用仿函數(shù)，就是使用對應(yīng)類的對象，所以我們需要?jiǎng)?chuàng)建compare類的對象com，并傳入比較內(nèi)容進(jìn)行比較。

這里要注意兩個(gè)比較數(shù)據(jù)的先后位置，要按照到底是誰大于誰而傳入正確的先后順序。

?

隨后就可以按照排序要求對類型進(jìn)行更改，按照我們的代碼方式，less為降序，greater為升序。?

總結(jié)

優(yōu)先級隊(duì)列的分享到這里就結(jié)束啦。

目前為止不難看出C++的這些容器的底層數(shù)據(jù)結(jié)構(gòu)都是我們所學(xué)習(xí)過的，所以對于掌握容器的使用并不困難。

喜歡本篇文章記得一鍵三連，我們下期再見~

柚子快報(bào)邀請碼778899分享：開發(fā)語言 C++——優(yōu)先級隊(duì)列

http://yzkb.51969.com/

參考文章