歡迎光臨
每天分享高質量文章

漫畫:什麼是優先佇列?

(點擊上方公眾號,可快速關註)


來源:程式員小灰


在之前的漫畫中,我們介紹了二叉堆和堆排序。沒看過的小伙伴可以看一看前文:


漫畫:什麼是二叉堆?


漫畫:什麼是堆排序?


這一次,我們來講一講二叉堆的另外一個應用:優先佇列






佇列的特點是什麼?


聰明的小伙伴們都知道,是先進先出(FIFO)


入佇列:




出佇列:




那麼,優先佇列又是什麼樣子呢?


優先佇列不再遵循先入先出的原則,而是分為兩種情況:


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

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


比如有一個最大優先佇列,它的最大元素是8,那麼雖然元素8並不是隊首元素,但出隊的時候仍然讓元素8首先出隊:





要滿足以上需求,利用線性資料結構並非不能實現,但是時間複雜度較高,最壞時間複雜度O(n),並不是最理想的方式。


至於為什麼最壞時間複雜度是O(n),大家可以思考下。





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


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

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


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


入隊操作:


1.插入新節點5




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




出隊操作:


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




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





3.節點1下沉,節點9成為新堆頂










public class PriorityQueue {

  1. private int[] array;

  2. private int size;


  3. public PriorityQueue(){

  4.    //佇列初始長度32

  5.    array = new int[32];

  6. }


  7. /**

  8. * 入隊

  9. * @param key  入隊元素

  10. */

  11. private void enQueue(int key) {

  12.    //佇列長度超出範圍,擴容

  13.    if(size >= array.length){

  14.        resize();

  15.    }

  16.    array[size++] = key;

  17.    upAdjust();

  18. }


  19. /**

  20. * 出隊

  21. */

  22. private int deQueue() throws Exception {

  23.    if(size <= 0){

  24.        throw new Exception("the queue is empty !");

  25.    }

  26.    //獲取堆頂元素

  27.    int head = array[0];

  28.    //最後一個元素移動到堆頂

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

  30.    downAdjust();

  31.    return head;

  32. }


  33. /**

  34. * 上浮調整

  35. */

  36. private void upAdjust() {

  37.    int childIndex = size-1;

  38.    int parentIndex = childIndex/2;

  39.    // temp儲存插入的葉子節點值,用於最後的賦值

  40.    int temp = array[childIndex];

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

  42.    {

  43.        //無需真正交換,單向賦值即可

  44.        array[childIndex] = array[parentIndex];

  45.        childIndex = parentIndex;

  46.        parentIndex = parentIndex / 2;

  47.    }

  48.    array[childIndex] = temp;

  49. }


  50. /**

  51. * 下沉調整

  52. */

  53. private void downAdjust() {

  54.    // temp儲存父節點值,用於最後的賦值

  55.    int parentIndex = 0;

  56.    int temp = array[parentIndex];

  57.    int childIndex = 1;

  58.    while (childIndex < size) {

  59.        // 如果有右孩子,且右孩子大於左孩子的值,則定位到右孩子

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

  61.            childIndex++;

  62.        }

  63.        // 如果父節點大於任何一個孩子的值,直接跳出

  64.        if (temp >= array[childIndex])

  65.            break;

  66.        //無需真正交換,單向賦值即可

  67.        array[parentIndex] = array[childIndex];

  68.        parentIndex = childIndex;

  69.        childIndex = 2 * childIndex + 1;

  70.    }

  71.    array[parentIndex] = temp;

  72. }


  73. /**

  74. * 下沉調整

  75. */

  76. private void resize() {

  77.    //佇列容量翻倍

  78.    int newSize = this.size * 2;

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

  80. }


  81. public static void main(String[] args) throws Exception {

  82.    PriorityQueue priorityQueue = new PriorityQueue();

  83.    priorityQueue.enQueue(3);

  84.    priorityQueue.enQueue(5);

  85.    priorityQueue.enQueue(10);

  86.    priorityQueue.enQueue(2);

  87.    priorityQueue.enQueue(7);

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

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

  90. }

}


代碼中採用陣列來儲存二叉堆的元素,因此當元素超過陣列範圍的時候,需要進行resize來擴大陣列長度。



【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:

http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂

© 2021 知識星球   网站地图