什么是優(yōu)先隊(duì)列？漫畫形式帶你詳細(xì)了解優(yōu)先隊(duì)列

這一次，我們來講一講二叉堆的另外一個應(yīng)用：優(yōu)先隊(duì)列

隊(duì)列的特點(diǎn)是什么？

聰明的小伙伴們都知道，是先進(jìn)先出（FIFO）。

入隊(duì)列：

出隊(duì)列：

那么，優(yōu)先隊(duì)列又是什么樣子呢？

優(yōu)先隊(duì)列不再遵循先入先出的原則，而是分為兩種情況：

最大優(yōu)先隊(duì)列，無論入隊(duì)順序，當(dāng)前最大的元素優(yōu)先出隊(duì)。

最小優(yōu)先隊(duì)列，無論入隊(duì)順序，當(dāng)前最小的元素優(yōu)先出隊(duì)。

比如有一個最大優(yōu)先隊(duì)列，它的最大元素是8，那么雖然元素8并不是隊(duì)首元素，但出隊(duì)的時候仍然讓元素8首先出隊(duì)：

要滿足以上需求，利用線性數(shù)據(jù)結(jié)構(gòu)并非不能實(shí)現(xiàn)，但是時間復(fù)雜度較高，最壞時間復(fù)雜度O（n），并不是最理想的方式。

至于為什么最壞時間復(fù)雜度是O（n），大家可以思考下。

讓我們回顧一下二叉堆的特性：

1.最大堆的堆頂是整個堆中的最大元素

2.最小堆的堆頂是整個堆中的最小元素

因此，我們可以用最大堆來實(shí)現(xiàn)最大優(yōu)先隊(duì)列，每一次入隊(duì)操作就是堆的插入操作，每一次出隊(duì)操作就是刪除堆頂節(jié)點(diǎn)。

入隊(duì)操作：

1.插入新節(jié)點(diǎn)5

2.新節(jié)點(diǎn)5上浮到合適位置。

出隊(duì)操作：

1.把原堆頂節(jié)點(diǎn)10“出隊(duì)”

2.最后一個節(jié)點(diǎn)1替換到堆頂位置

3.節(jié)點(diǎn)1下沉，節(jié)點(diǎn)9成為新堆頂

public class PriorityQueue {

privateint[] array;

privateint size;

publicPriorityQueue(){

//隊(duì)列初始長度32

array =newint[32];

}

/**

* 入隊(duì)

* @param key 入隊(duì)元素

*/

privatevoid enQueue(int key){

//隊(duì)列長度超出范圍，擴(kuò)容

if(size >= array.length){

resize();

}

array[size++]= key;

upAdjust();

}

/**

* 出隊(duì)

*/

privateint deQueue()throwsException{

if(size <=0){

thrownewException("the queue is empty !");

}

//獲取堆頂元素

int head = array[0];

//最后一個元素移動到堆頂

array[0]= array[--size];

downAdjust();

return head;

}

/**

* 上浮調(diào)整

*/

privatevoid upAdjust(){

int childIndex = size-1;

int parentIndex = childIndex/2;

// temp保存插入的葉子節(jié)點(diǎn)值，用于最后的賦值

int temp = array[childIndex];

while(childIndex >0&& temp > array[parentIndex])

{

//無需真正交換，單向賦值即可

array[childIndex]= array[parentIndex];

childIndex = parentIndex;

parentIndex = parentIndex /2;

}

array[childIndex]= temp;

}

/**

* 下沉調(diào)整

*/

privatevoid downAdjust(){

// temp保存父節(jié)點(diǎn)值，用于最后的賦值

int parentIndex =0;

int temp = array[parentIndex];

int childIndex =1;

while(childIndex < size){

// 如果有右孩子，且右孩子大于左孩子的值，則定位到右孩子

if(childIndex +1< size && array[childIndex +1]> array[childIndex]){

childIndex++;

}

// 如果父節(jié)點(diǎn)大于任何一個孩子的值，直接跳出

if(temp >= array[childIndex])

break;

//無需真正交換，單向賦值即可

array[parentIndex]= array[childIndex];

parentIndex = childIndex;

childIndex =2* childIndex +1;

}

array[parentIndex]= temp;

}

/**

* 下沉調(diào)整

*/

privatevoid resize(){

//隊(duì)列容量翻倍

int newSize =this.size *2;

this.array =Arrays.copyOf(this.array, newSize);

}

publicstaticvoid main(String[] args)throwsException{

PriorityQueue priorityQueue =newPriorityQueue();

priorityQueue.enQueue(3);

priorityQueue.enQueue(5);

priorityQueue.enQueue(10);

priorityQueue.enQueue(2);

priorityQueue.enQueue(7);

System.out.println("出隊(duì)元素："+ priorityQueue.deQueue());

System.out.println("出隊(duì)元素："+ priorityQueue.deQueue());

}

}

代碼中采用數(shù)組來存儲二叉堆的元素，因此當(dāng)元素超過數(shù)組范圍的時候，需要進(jìn)行resize來擴(kuò)大數(shù)組長度。

—————END—————

●編號755，輸入編號直達(dá)本文

●輸入m獲取文章目錄

推薦↓↓↓

人工智能與大數(shù)據(jù)技術(shù)

更多推薦《18個技術(shù)類公眾微信》

涵蓋：程序人生、算法與數(shù)據(jù)結(jié)構(gòu)、黑客技術(shù)與網(wǎng)絡(luò)安全、大數(shù)據(jù)技術(shù)、前端開發(fā)、Java、Python、Web開發(fā)、安卓開發(fā)、iOS開發(fā)、C/C++、.NET、Linux、數(shù)據(jù)庫、運(yùn)維等。