優先級隊列-堆【資料結構】

前言：

我們之前學習的普通的隊列，元素是先進先出；而優先級隊列，是按照順序進，優先級最高的先出隊列，優先級相同再遵循先進先出

優先級隊列，名字叫隊列，本質上是一個特殊的二叉樹(堆)

舉例：

幼稚園放學時，家長去接娃，整整齊齊的排着隊等着進去接娃，突然來了一位校上司進學校有事…

.

二叉樹的順序存儲

之前我們學習了二叉樹的表示方法：左右孩子表示法，每個節點均記錄左右子樹的根節點引用

除此之外，我們也可以使用數組來表示一棵樹

使用數組存儲這棵樹的層序變量結果(包含空節點)

但是，使用數組來表示樹，可能會浪費很多的空間

比如：

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

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

目錄

• 堆(heap)
• • 概念
  • 操作
  • • 向下調整
    • 建堆
    • 向上調整 (以大堆為例)
  • 使用堆模拟實作優先級隊列
  • 标準庫中的優先隊列
  • topK 問題
  • • 查找和最小的K對數字

堆(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所在的包：

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;
}