優先級佇列（堆）

1、掌握堆的概念和實作

2、掌握PriorityQueue的使用

一、概念

堆邏輯上是一課完全二叉樹，是用二叉樹的層序遍歷方式放入陣列中，也就是說是用順序陣列來存盤，這樣可以節省空間，

重要公式：

1、已知父親節點小標是i

左孩子下標：2*i+1；

右孩子下標：2*i+2；

2、已知孩子節點是j

求父親節點的下標：

父親節點下標：（j-1）/2

1.1 堆的分類

小堆：（小根堆，最小堆）父親節點小于左右孩子節點，注意的是左右孩子沒有大小關系；

大堆：（大根堆，最大堆）父親節點大于左右孩子節點，注意的是左右孩子沒有大小關系；

1.2向下調整

以向下調整實作堆的程序，以大根堆為例：

這里只演示了一半，完整版檔案太大傳不了😂😂😂😂，知道思想差不多也可以推了

向下調整，是每顆子樹向下調整：

1、最開始調整的時候，是從最后一個子樹開始調整；

2、有個很重要的公式是：找到最后一個子樹的根節點

parent=（length-1-1）/2

向下調整代碼如下：

 //大根堆是向下調整
    public void shiftDown(int parent) {
        int chlid=2*parent+1;//之前推了孩子公式

        //會有回圈，條件是child小于陣列才能操作
        while(chlid<this.usedSize) {
            //判斷有沒有右孩子，然后比較左右孩子的大小
            if(chlid+1<this.usedSize && this.elem[chlid]<this.elem[chlid+1]) {
                chlid++;
            }
            //走到這，子數已經是最大值，剩下的就是交換
            if(this.elem[chlid]>this.elem[parent]) {
                int tmp=this.elem[parent];
                this.elem[parent]=this.elem[chlid];
                this.elem[chlid]=tmp;
                parent=chlid;
                chlid=2*parent+1;
            } else {
                break;
            }
        }
    }

時間復雜度：一般都是最壞的情況，是從根一路遍歷底層，所以就是完全二叉樹的高度O（log(n)）

1.3 建堆

完整代碼(大根堆）：

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem=new int[10];

    }
    public void creatBigHeap(int[] array) {
        for(int i=0;i<array.length;i++) {
            this.elem[i]=array[i];
            this.usedSize++;
        }

        for(int i=(this.usedSize-1-1)/2;i>=0;i--) {
            shiftDown(i);
        }
    }
    //大根堆是向下調整
    public void shiftDown(int parent) {
        int chlid=2*parent+1;

        //會有回圈，條件是child小于陣列才能操作
        while(chlid<this.usedSize) {
            //判斷有沒有右孩子，比較左右孩子的大小
            if(chlid+1<this.usedSize && this.elem[chlid]<this.elem[chlid+1]) {
                chlid++;
            }
            //走到這，子數已經是最大值，剩下的就是交換
            //這是大根堆，小根堆大于小于號改變一下就行了
            if(this.elem[chlid]>this.elem[parent]) {
                int tmp=this.elem[parent];
                this.elem[parent]=this.elem[chlid];
                this.elem[chlid]=tmp;
                parent=chlid;
                chlid=2*parent+1;
            } else {
                break;
            }
        }
}

時間復雜度：向下調整+回圈：O(n * log(n))

實際上是O（n）

想了解可以看這個鏈接：堆排序中建堆程序時間復雜度O(n)怎么來的？

二、入佇列

思路：把入佇列的元素，放到陣列的最后一個位置,保證這個堆是大根堆或者是小根堆，先判斷順序陣列滿不滿,滿就擴容,然后實作向上調整

2.1 向上調整

思路:定義孩子節點,和父親節點,新的元素與父親節點比較,大就交換,然后更新child,使child=parent

代碼:

 public void shiftUp(int child) {
        int parent = (child-1)/2;
        while (parent >= 0) {
            if(this.elem[child] > this.elem[parent]) {
                int tmp = this.elem[child];
                this.elem[child] = this.elem[parent];
                this.elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }

三、出佇列

思路：因為是優先級佇列，所以是出堆頂元素，用堆頂元素跟陣列最后一個元素交換，再usedSize–，此時雖然交換完，但是他不是大根堆或者小根堆，所以用向下調整0下標這課樹，來保證最后是大根堆，

代碼：

 public int poll() {
        if(isEmpty()) {//佇列為空拋出例外
            throw new RuntimeException("佇列為空！");
        }
     //交換
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;
     //向下調整
        shiftDown(0);
        return tmp;
    }