這一次，我們來講一講二叉堆的另外一個應用：優先隊列

隊列的特點是什么？

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

入隊列：

出隊列：

那么，優先隊列又是什么樣子呢？

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

最大優先隊列，無論入隊順序，當前最大的元素優先出隊。

最小優先隊列，無論入隊順序，當前最小的元素優先出隊。

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

要滿足以上需求，利用線性數據結構并非不能實現，但是時間復雜度較高，最壞時間復雜度O（n），并不是最理想的方式。

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

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

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

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

因此，我們可以用最大堆來實現最大優先隊列，每一次入隊操作就是堆的插入操作，每一次出隊操作就是刪除堆頂節點。

入隊操作：

1.插入新節點5

2.新節點5上浮到合適位置。

出隊操作：

1.把原堆頂節點10“出隊”

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

3.節點1下沉，節點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;

}

/**

* 上浮調整

*/

privatevoid upAdjust(){

int childIndex = size-1;

int parentIndex = childIndex/2;

// temp保存插入的葉子節點值，用于最后的賦值

int temp = array[childIndex];

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

{

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

array[childIndex]= array[parentIndex];

childIndex = parentIndex;

parentIndex = parentIndex /2;

}

array[childIndex]= temp;

}

/**

* 下沉調整

*/

privatevoid downAdjust(){

// temp保存父節點值，用于最后的賦值

int parentIndex =0;

int temp = array[parentIndex];

int childIndex =1;

while(childIndex < size){

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

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

childIndex++;

}

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

if(temp >= array[childIndex])

break;

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

array[parentIndex]= array[childIndex];

parentIndex = childIndex;

childIndex =2* childIndex +1;

}

array[parentIndex]= temp;

}

/**

* 下沉調整

*/

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());

}

}

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

—————END—————

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

●輸入m獲取文章目錄

推薦↓↓↓

人工智能與大數據技術

更多推薦《18個技術類公眾微信》

涵蓋：程序人生、算法與數據結構、黑客技術與網絡安全、大數據技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、數據庫、運維等。