硬核！手寫一個優先佇列

文章收錄在首發公眾號：bigsai 期待你的到訪！

前言

事情還要從一個故事講起：

對於上面那隻可愛的小狗狗不會，本篇即為該教學，首先，我要告訴這隻可愛的小狗狗，這種問題你要使用的資料結構為優先佇列，每次操作的時間複雜度為O(logn),而整個過程的時間複雜度為O(nlogn).

對於本片的設計與實現和堆排序可能有些相似，因為他們都藉助堆來實現演演算法和資料結構，下面詳細介紹優先佇列的設計與實現。

堆

而堆就是一類特殊的資料結構的統稱。堆通常是一個可以被看做一棵樹(完全)的陣列物件。且總是滿足以下規則：

• 堆總是一棵完全二元樹
• 每個節點總是大於(或小於)它的孩子節點。

對於完全二元樹，我想大家都能明白，就是最底層葉子節點要嚴格按照從左向右來。

堆有大根堆和小根堆，如果是所有父節點都大於子節點的時候，那麼這就是個大根堆，反之則為小根堆，以下就是一個大根堆：

最後需要注意的是我們並不是用鏈式去儲存這個二元樹而是用陣列去儲存這個樹，雖然鏈式的使用場景可能更多一些，但是在完全二元樹的情況下空間使用率較好沒有斜樹的出現。並且在操作的時候可以直接通過編號找到位置進行交換。

優先佇列

如何理解優先佇列，我們先從一段對話說起：

優先佇列，它是一個佇列。而普通的佇列遵從先進先出的規則。而優先佇列遵循一個排序的規則：每次丟擲自定義排序最大(小)的，預設的情況是丟擲最小的，本篇也就從最基本的原理進行分析。

並且它的用法佇列還是一樣的，，所以我們在設計這個類的時候api方面要與佇列的api一致。

我們主要實現add、poll、和peek方法，並且會著重於演演算法的實現而不太著重一些細節的實現。

雖然優先佇列和堆排序利用堆結構特性的流程有一些相似，但是兩者其實還是有些操作上的區別的：

堆排序 ：

• 剛開始是一個雜亂無章的序列，所以需要將雜亂的序列（樹）通過一個方法變成一個合法的堆。
• 轉成一個堆之後需要刪除n次每次刪除完都要重新調整這個堆。沒有插入操作。

優先佇列：

• 佇列（堆）剛開始的內容為空，每次增加一個元素時需要即使調整堆。每次刪除也要及時調整堆，增加和刪除每次都只是一個元素。

但是優先佇列的具體操作流程是如何的呢？我們具體分析其插入和刪除的流程。

插入add流程(小根堆為例)：

• 正常處理完的優先佇列內的資料滿足一個堆的結構，所以就是插入在堆中。
• 堆是一棵完全二元樹，所以在插入初始，插入到最後一個位置不影響其他結構。
• 節點和父節點比較大小(父節點索引為其二分之一)。如果該節點比父節點更小，則交換資料，一直到不能交換為止，這個過程不用擔心不合法，因為父節點更小的話更滿足比孩子節點更小。

刪除pop流程(小根堆為例)：

• pop刪除操作取優先佇列內最小的元素，而這個元素肯定就是堆頂元素了，取完之後，這個堆的其他部分還是滿足堆的結構但是缺少堆頂。
• 為了不影響整個結構，我們將末尾的那個元素移到堆頂，此時堆需要調整使其滿足堆的性質條件。
• 交換的這個節點和左右孩子進行比較，如果需要交換則交換，交換後再次考慮交換子節點是否需要交換，一直到不交換為止。最壞情況是交換到根節點，這個複雜度每次為O(logn).

程式碼實現

我想到這裡，優先佇列的內部流程思想你已經掌握了，但是懂優先佇列原理和手寫優先佇列是兩個概念，為了更深入的學習優先佇列，在這裡就帶你手寫一個簡易型的優先佇列。

在程式碼的具體實現方面，最主要的就是pop()和add()兩個函數了。在pop()函數具體實現的時候，將最後一個元素移到堆頭考慮和其他孩子節點交換的時候，用while進行操作的時候計算孩子下標的時候要確保不越界。我們用的是陣列儲存資料，優先佇列的長度不一定等於這個陣列的長度。

而在實現add()函數的時候，這裡簡單的考慮了一下擴容。

具體實現的程式碼為：

import java.util.Arrays;

public class priQueue {

    private  int size;//優先佇列的大小
    private  int capacity;//陣列的容量
    private  int value[];//儲存的值

    public priQueue() {
        this.capacity = 10;
        this.value = new int[capacity];
        this.size=0;
    }
    public priQueue(int capacity) {
        this.capacity = capacity;
        this.value = new int[capacity];
        this.size=0;
    }

    /**
     * 插入元素
     * @param number
     */
    public void add(int number) {
        if(size==capacity)//擴容
        {
            capacity*=1.5;
            value= Arrays.copyOf(value,capacity);
        }
        value[size++]=number;//先加到末尾
        int index=size-1;
        while (index>=1) {//進行交換
            if(value[index]<value[index/2]) {
                swap(index,index/2,value);
                index=index/2;
            }
            else//不需要交換即停止
                break;
        }
    }
    public int peek() {
        return  value[0];
    }

    /**
     * 丟擲隊頭
     * @return
     */
    public int pop() {
        int val=value[0];//呆返回資料額
        value[0]=value[--size];//將最後一個元素賦值在堆頭
        int index=0,leftChild=0,rightChild=0;
        while (true)
        {
            leftChild=index*2+1;
            rightChild=index*2+2;
            if(leftChild>=size)//左孩子必須滿足在條件內
                break;
            else if(rightChild<size&&value[rightChild]<value[index]&&value[rightChild]<value[leftChild])
            {//右孩子更小
                swap(index,rightChild,value);
                index=rightChild;
            }
            else if(value[leftChild]<value[index])
            {//左孩子更小
                swap(index,leftChild,value);
                index=leftChild;
            }
            else //不需要 它自己最小
                break;
        }
        return  val;
    }
    //交換兩個元素
    public  void swap(int i,int j,int arr[]) {
        int team=arr[i];
        arr[i]=arr[j];
        arr[j]=team;
    }

    public int size() {
        return  size;
    }
}

寫個類測試一下看看：

結語

本次優先佇列介紹就到這裡啦，感覺不錯記得點贊或一鍵三連哦，建議和堆排序一起看和學習效果更佳，要能夠手寫程式碼。個人公眾號：bigsai 回覆 bigsai 更多精彩和資源與你分享。