前言：
我們之前學習的普通的佇列，元素是先進先出；而優先級佇列，是按照順序進，優先級最高的先出佇列，優先級相同再遵循先進先出
優先級佇列，名字叫佇列，本質上是一個特殊的二叉樹(堆)

舉例：
幼兒園放學時，家長去接娃，整整齊齊的排著隊等著進去接娃，突然來了一位校領導進學校有事…
.

二叉樹的順序存盤

之前我們學習了二叉樹的表示方法：左右孩子表示法，每個節點均記錄左右子樹的根節點參考
除此之外，我們也可以使用陣列來表示一棵樹

使用陣列存盤這棵樹的層序變數結果(包含空節點)

但是，使用陣列來表示樹，可能會浪費很多的空間
比如：

對于一般的普通的樹來說，使用陣串列示，可能會造成空間的浪費，但是對于一種特殊的樹(完全二叉樹)來說，使用陣列來表示就剛剛好，不會造成空間的浪費

完全二叉樹： 和滿二叉樹相比，右側缺了一個 “豁” (哈哈哈，比較容易理解~~)

堆(heap)

概念

在 JVM 記憶體區域劃分(JVM記憶體模型 JMM)中，我們提到了方法區、堆疊區、堆區，程式計數器…
但是，今天提到的 堆 和 JVM 記憶體區域劃分中的堆沒關系 (此堆非彼堆)

堆(heap)，是資料結構中的通用概念，本質上是一個二叉樹
.

• 是一個完全二叉樹
• 對于任意節點，滿足根節點小于左右子樹的值(小堆) 或 滿足根節點大于左右子樹的值(大堆)
• 堆通常是通過陣列的形式來存盤的
• 堆的最大用處：能夠讓我們快速找到樹中的最大值或者最小值 (堆頂元素)
  還能幫我們高效的找出前 K 大 / 小 元素 topK問題

topK 問題

操作

向下調整

把不滿足堆的結構調整成滿足堆的結構

前提： 左右子樹必須已經是一個堆，才能調整

程序：

• 設定根節點為當前節點 cur
• 比較其左右子樹的值，使用 minChild 來標記較小的值
• 比較 minChild 和 cur 的值
  若 cur < minChild，即符合小堆規則，不進行交換，調整結束
  若 cur > minChild，不符合小堆規則，將其進行交換

代碼實作：

時間復雜度： O(logN) — cur 固定，minChild 每次 x 2

private
 static void shiftDown(int[] array,int size,int index){
    // size 表示有效堆的 堆元素個數
    // index 表示從哪個位置的下標開始調整
    // cur 從 index 這里出發
    int cur = index;
    // 根據cur下標找到左子樹的下標
    int minChild = cur * 2 + 1;
    while(minChild < size){
        //比較左右子樹，找到較小值
        if(minChild + 1 < size && array[minChild + 1] < array[minChild]){
            minChild = minChild + 1;
        }
        // 此時minChild下標對應左右子樹的較小值的下標
        // 比較 minChild 和 cur 的值
        if(array[cur] > array[minChild]){
            int tmp = array[minChild];
            array[minChild] = array[cur];
            array[cur] = tmp;
        }
        //調整結束
        else {
            break;
        }
        //更新 cur 和minChild
        cur = minChild;
        minChild = cur * 2 + 1;
    }
}

建堆

借助向下調整，就可以把一個陣列構造成堆，從倒數第一個非葉子節點開始，從后往前遍歷陣列，針對每個位置，依次向下調整即可

舉例： 將陣列 [ 9，5，2，7，3，6，8 ] 建成一個小堆
程序分析：

代碼實作：

public static void createHeap(int[] array,int size){
    for (int i = (size - 1 - 1) / 2;i >= 0; i--) {
        shiftDown(array,size,i);
    }
}

時間復雜度： 回圈呼叫向下調整方法，時間復雜度看起來像是 O(logN*N)，但實際上是O(N) (復雜的數學推導程序)

向上調整 (以大堆為例)

程序：

• 設當前節點 cur
• 比較 cur 和其父節點 parent 的值
  若 cur < parent，不符合大堆規則，將其進行交換
  若 cur > parent，即符合大堆規則，不進行交換，調整結束

由上可看出，向上調整比向下調整要簡單些，直接比較父子節點即可

代碼實作：

此處發現，沒有用到 size引數，判定調整結束，只需要和 0 比較即可，不需要知道整個堆有多大

//向上調整
private static void shiftUp(int[] array,int size,int index){
    int cur = index;
    int parent = (cur - 1) / 2;
    while(cur > 0){
        //父親比孩子大，不符合大堆要求
        if(array[parent] < array[cur]){
            //交換
            int tmp = array[parent];
            array[parent] = array[cur];
            array[cur] = tmp;
        }
        else{
            break;
        }
        cur = parent;
        parent = (cur - 1) / 2;
    }
}

使用堆模擬實作優先級佇列

• 入佇列

public void offer(int x){
    array[size] = x;
    size++;
    //把新加入的元素向上調整
    shiftUp(array,size-1);
}

• 出佇列

隊首元素刪掉的同時，滿足剩下的結構仍然是一個堆

//出佇列
public int poll(){
    //下標為0的元素即為堆頂元素
    int deleteVal = array[0];
    // 將最后一個元素 bia 到 堆頂元素
    array[0] = array[size - 1];
    size--;
    shiftDown(array,size,0);
    return deleteVal;
}

• 取堆頂元素

public int peek(){
    return array[0];
}

main方法驗證：

public static void main(String[] args) {
    MyPriorityQueue queue = new MyPriorityQueue();
    queue.offer(9);
    queue.offer(5);
    queue.offer(2);
    queue.offer(7);
    queue.offer(3);
    queue.offer(6);
    queue.offer(8);

    //依次出佇列
    while(!queue.isEmpty()){
        int cur = queue.poll();
        System.out.print(cur + " ");
    }
}

堆(優先佇列)，每次poll一個元素都是把優先級最高 / 低的元素取出來，能幫我們解決 topK 問題，如果你 poll 了 n 次的話，就相當于對原來的序列進行了排序 — 堆排序

標準庫中的優先佇列

• 使用時必須匯入PriorityQueue所在的包：

import java.util.PriorityQueue;

PriorityQueue是執行緒不安全的，而PriorityBlockingQueue是執行緒安全的

代碼示例：

import java.util.PriorityQueue;

public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(7);
        queue.offer(3);
        queue.offer(6);
        queue.offer(8);
        while(!queue.isEmpty()){
            int cur = queue.poll();
            System.out.print(cur + " ");
        }
    }
}

輸出結果：

我們會發現，在標準庫中，優先佇列，默認是以小堆實作的

• 不能插入null物件，否則會拋出NullPointerException例外

• 不能插入無法比較大小的物件，否則會拋出ClassCastException例外

topK 問題

經典 topK 問題：
給定你 100 億個數字，找出其中前1000大的元素(不考慮記憶體空間)

方法1:
用一個陣列保存這100億個數字，直接在這個陣列上建大堆，回圈1000次取出堆頂元素 + 調整操作，即可得到前1000大元素

方法2:

先取集合中的前1000個元素放到一個陣列中，建一個小堆
一個一個遍歷集合中的數字，將其和堆頂元素進行比較，若某個元素比堆頂元素大，就把堆頂元素洗掉(調整堆)，當所有元素遍歷完后，堆中元素就是前1000大元素

時間復雜度分析：
假設給定 N 個元素，取前 M 大個元素 ( N 遠大于M )

由上邊的分析可見，方法2的效率更高

查找和最小的K對數字

在線OJ

思考：

• 獲取到所有的數對
• 把數對放到優先佇列中
  把數對放在一個類中，優先佇列保存這個類即可
• 從優先佇列中取前K對數對即可
  回傳值的二維陣列中，每一行是一個數對(兩個元素)，一共有K行

代碼實作：

以方法1 為例：

class Pair implements Comparable<Pair> {
    public int n1;
    public int n2;
    public int sum;

    public Pair(int n1, int n2) {
        this.n1 = n1;
        this.n2 = n2;
        this.sum = n1 + n2;
    }

    @Override
    public int compareTo(Pair o) {
        //this 比 other 小，回傳 < 0
        //this 比 other 大，回傳 > 0
        //this == other ，回傳  0
        return this.sum - o.sum;
    }
}

public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
    List<List<Integer>> result = new ArrayList<>();
    //判斷 nums1 nums2合法性
    if(nums1.length == 0 || nums2.length == 0 || k <= 0){
        return result;
    }
    //建立一個小堆
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    //獲取到所有可能的數對,并加入到佇列中
    for (int i = 0; i < nums1.length; i++) {
        for (int j = 0; j < nums2.length; j++) {
            queue.offer(new Pair(nums1[i],nums2[j]));
        }
    }
    //回圈取出前k項元素
    for (int i = 0; i < k && !queue.isEmpty(); i++) {
        Pair cur = queue.poll();
        List<Integer> tmp = new ArrayList<>();
        tmp.add(cur.n1);
        tmp.add(cur.n2);
        result.add(tmp);
    }
    return result;
}