硬核！手寫一個優先佇列

文章收錄在首發公眾號：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 更多精彩和資源與你分享，