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

隊列的特點是什么？

聰明的小伙伴們都知道，是先進先出（FIFO）。

入隊列：

出隊列：

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

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

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

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

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

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

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

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

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

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

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

入隊操作：

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

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

出隊操作：

1.把原堆頂節(jié)點10“出隊”

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

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

public class PriorityQueue {

privateint[] array;

privateint size;

publicPriorityQueue(){

//隊列初始長度32

array =newint[32];

}

/**

* 入隊

* @param key 入隊元素

*/

privatevoid enQueue(int key){

//隊列長度超出范圍，擴容

if(size >= array.length){

resize();

}

array[size++]= key;

upAdjust();

}

/**

* 出隊

*/

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é)點值，用于最后的賦值

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é)點值，用于最后的賦值

int parentIndex =0;

int temp = array[parentIndex];

int childIndex =1;

while(childIndex < size){

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

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

childIndex++;

}

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

if(temp >= array[childIndex])

break;

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

array[parentIndex]= array[childIndex];

parentIndex = childIndex;

childIndex =2* childIndex +1;

}

array[parentIndex]= temp;

}

/**

* 下沉調(diào)整

*/

privatevoid resize(){

//隊列容量翻倍

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("出隊元素："+ priorityQueue.deQueue());

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

}

}

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

—————END—————

●編號755，輸入編號直達本文

●輸入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ù)庫、運維等。