什么是優(yōu)先隊(duì)列

我們都知道隊(duì)列是一種先進(jìn)先出绘雁、后進(jìn)后出的數(shù)據(jù)結(jié)構(gòu)，就如同日常生活中的排隊(duì)一樣，先到先得扫步。而優(yōu)先隊(duì)列則是一種特殊的隊(duì)列，優(yōu)先隊(duì)列與普通隊(duì)列最大的不同點(diǎn)就在于出隊(duì)順序不一樣匈子。

因?yàn)閮?yōu)先隊(duì)列的出隊(duì)順序與入隊(duì)順序無(wú)關(guān)河胎，和優(yōu)先級(jí)有關(guān)。也就是按元素的優(yōu)先級(jí)決定其出隊(duì)順序虎敦，優(yōu)先級(jí)高的先出隊(duì)游岳，優(yōu)先級(jí)低的后出隊(duì)，這也是為什么這種數(shù)據(jù)結(jié)構(gòu)叫優(yōu)先隊(duì)列的原因其徙。

這就好比現(xiàn)實(shí)生活中在銀行排隊(duì)辦理業(yè)務(wù)胚迫，持有金卡的客戶可以優(yōu)先于普通卡的客戶被接待，而鉆石卡的客戶又優(yōu)先于金卡的客戶唾那，以此類推访锻。這就是一種優(yōu)先隊(duì)列。

應(yīng)用場(chǎng)景：

• 優(yōu)先隊(duì)列的應(yīng)用場(chǎng)景非常多闹获，比如期犬，任務(wù)調(diào)度器、赫夫曼編碼避诽、圖的最短路徑哭懈、最小生成樹(shù)算法等等。不僅如此茎用，很多語(yǔ)言中遣总，都提供了優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)睬罗，比如，Java 的 PriorityQueue旭斥，C++ 的 priority_queue 等容达。

堆的基礎(chǔ)表示

堆（Heap）簡(jiǎn)單來(lái)說(shuō)是一種特殊的樹(shù)，那么什么樣的樹(shù)才是堆呢垂券？我羅列了兩點(diǎn)要求花盐，只要滿足這兩點(diǎn)，它就是一個(gè)堆：

• 堆是一個(gè)完全二叉樹(shù)菇爪。完全二叉樹(shù)：把元素順序排列成樹(shù)的形狀
• 堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于（或小于等于）其子樹(shù)中每個(gè)節(jié)點(diǎn)的值

第一點(diǎn)算芯，堆必須是一個(gè)完全二叉樹(shù)。還記得我們之前講的完全二叉樹(shù)的定義嗎凳宙？完全二叉樹(shù)要求熙揍，除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的氏涩，最后一層的節(jié)點(diǎn)都靠左排列届囚。

第二點(diǎn)，堆中的每個(gè)節(jié)點(diǎn)的值必須大于等于（或者小于等于）其子樹(shù)中每個(gè)節(jié)點(diǎn)的值是尖。實(shí)際上意系，我們還可以換一種說(shuō)法，堆中每個(gè)節(jié)點(diǎn)的值都大于等于（或者小于等于）其左右子節(jié)點(diǎn)的值饺汹。這兩種表述是等價(jià)的蛔添。

對(duì)于每個(gè)節(jié)點(diǎn)的值都大于等于子樹(shù)中每個(gè)節(jié)點(diǎn)值的堆，我們叫做“大頂堆”兜辞。對(duì)于每個(gè)節(jié)點(diǎn)的值都小于等于子樹(shù)中每個(gè)節(jié)點(diǎn)值的堆迎瞧，我們叫做“小頂堆”。

清楚了定義之后弦疮，我們來(lái)直觀的看一下什么是堆：

image.png

在上圖中夹攒，第 1 個(gè)和第 2 個(gè)是大頂堆蜘醋，第 3 個(gè)是小頂堆胁塞，第 4 個(gè)不是堆。除此之外压语，從圖中還可以看出來(lái)啸罢，對(duì)于同一組數(shù)據(jù)，我們可以構(gòu)建多種不同形態(tài)的堆胎食。

如何實(shí)現(xiàn)一個(gè)堆扰才？

堆的實(shí)現(xiàn)并不局限于某一種特定的方式，可以使用鏈?zhǔn)綐?shù)形結(jié)構(gòu)（節(jié)點(diǎn)有左右指針）實(shí)現(xiàn)厕怜，也可以使用數(shù)組實(shí)現(xiàn)衩匣，因?yàn)橥耆鏄?shù)的特性是一層一層按順序排列的蕾总，完全可以緊湊地放在數(shù)組中。而且基于數(shù)組實(shí)現(xiàn)堆是一種比較巧妙且高效的方式琅捏，也是最常用的方式生百。

用數(shù)組來(lái)存儲(chǔ)完全二叉樹(shù)是非常節(jié)省存儲(chǔ)空間的。因?yàn)槲覀儾恍枰鎯?chǔ)左右子節(jié)點(diǎn)的指針柄延，單純地通過(guò)數(shù)組的下標(biāo)蚀浆，就可以找到一個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)和父節(jié)點(diǎn)。如下圖所示：

image.png

從圖中我們可以看到節(jié)點(diǎn)的存放規(guī)律就是：數(shù)組中下標(biāo)為 的節(jié)點(diǎn)的左子節(jié)點(diǎn)搜吧，就是下標(biāo)為 的節(jié)點(diǎn)市俊，右子節(jié)點(diǎn)則是下標(biāo)為 的節(jié)點(diǎn)。所以反過(guò)來(lái)，其父節(jié)點(diǎn)也就是下標(biāo)為 的節(jié)點(diǎn)。

parent(i) = i / 2
left child(i) = 2 * i
right child(i) = 2 * i + 1

通過(guò)這種方式姥敛，我們只要知道根節(jié)點(diǎn)存儲(chǔ)的位置缰泡，這樣就可以通過(guò)下標(biāo)計(jì)算，把整棵樹(shù)都串起來(lái)厘托。一般情況下，為了方便計(jì)算子節(jié)點(diǎn)，根節(jié)點(diǎn)會(huì)存儲(chǔ)在下標(biāo)為 1 的位置勇吊。

如果從 0 開(kāi)始存儲(chǔ)，實(shí)際上處理思路是沒(méi)有任何變化的窍仰，唯一變化的就是計(jì)算子節(jié)點(diǎn)和父節(jié)點(diǎn)的下標(biāo)的公式改變了：如果節(jié)點(diǎn)的下標(biāo)是 汉规，那左子節(jié)點(diǎn)的下標(biāo)就是 ，右子節(jié)點(diǎn)的下標(biāo)就是 驹吮，父節(jié)點(diǎn)的下標(biāo)就是 ?针史。如下圖所示：

image.png

有了以上的認(rèn)知后，接下來(lái)碟狞，我們就可以先編寫一個(gè)堆的基礎(chǔ)框架代碼了：

package heap;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 基于數(shù)組實(shí)現(xiàn)的最大堆
 * 堆中的元素需要具有可比較性啄枕，所以需要實(shí)現(xiàn)Comparable
 * 在此實(shí)現(xiàn)中是從數(shù)組的下標(biāo)0開(kāi)始存儲(chǔ)元素，因?yàn)槭褂肁rrayList作為數(shù)組的角色
 *
 * @author 01
 * @date 2021-01-19
 **/
public class MaxHeap<E extends Comparable<E>> {

    /**
     * 使用ArrayList的目的是無(wú)需關(guān)注動(dòng)態(tài)擴(kuò)縮容邏輯
     */
    private final ArrayList<E> data;

    public MaxHeap(int capacity) {
        this.data = new ArrayList<>(capacity);
    }

    public MaxHeap() {
        this.data = new ArrayList<>();
    }

    /**
     * 返回對(duì)中的元素個(gè)數(shù)
     */
    public int size() {
        return data.size();
    }

    /**
     * 判斷堆是否為空
     */
    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * 根據(jù)傳入的index族沃，計(jì)算其父節(jié)點(diǎn)所在的下標(biāo)
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index-1 doesn't have parent.");

        }
        return (index - 1) / 2;
    }

    /**
     * 根據(jù)傳入的index频祝，計(jì)算其左子節(jié)點(diǎn)所在的下標(biāo)
     */
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    /**
     * 根據(jù)傳入的index，計(jì)算其右子節(jié)點(diǎn)所在的下標(biāo)
     */
    private int rightChild(int index) {
        return index * 2 + 2;
    }
}

向堆中添加元素和Sift Up

往堆中添加一個(gè)元素后脆淹，我們需要繼續(xù)滿足堆的兩個(gè)特性常空。如果我們把新添加的元素放到數(shù)組的最后，如下圖盖溺，是不是就不符合堆的特性了漓糙？

image.png

于是，我們就需要進(jìn)行調(diào)整烘嘱，讓其重新滿足堆的特性昆禽，這個(gè)過(guò)程就叫做堆化（heapify）蝗蛙。堆化實(shí)際上有兩種，從下往上（Sift Up）和從上往下（Sift Down）醉鳖。這里我先講從下往上的堆化方法歼郭。堆化非常簡(jiǎn)單，就是順著節(jié)點(diǎn)所在的路徑辐棒，向上或者向下病曾，對(duì)比，然后交換漾根。

看下面這張使用Sift Up方式的堆化過(guò)程分解圖泰涂。我們可以讓新插入的節(jié)點(diǎn)與父節(jié)點(diǎn)對(duì)比大小。如果不滿足子節(jié)點(diǎn)小于等于父節(jié)點(diǎn)的大小關(guān)系辐怕，我們就互換兩個(gè)節(jié)點(diǎn)逼蒙。一直重復(fù)這個(gè)過(guò)程，直到父子節(jié)點(diǎn)之間滿足剛說(shuō)的那種大小關(guān)系：

image.png

將這個(gè)流程翻譯成具體的實(shí)現(xiàn)代碼如下：

/**
 * 向堆中添加元素 e
 */
public void add(E e) {
    data.add(e);
    siftUp(data.size() - 1);
}

/**
 * 從下往上調(diào)整元素的位置寄疏，直到元素到達(dá)根節(jié)點(diǎn)或小于父節(jié)點(diǎn)
 */
private void siftUp(int k) {
    while (k > 1 && isParentLessThan(k)) {
        // 交換 k 與其父節(jié)點(diǎn)的位置
        Collections.swap(data, k, parent(k));
        k = parent(k);
    }
}

/**
 * 判斷 k 的父節(jié)點(diǎn)是否小于 k
 */
private boolean isParentLessThan(int k) {
    return data.get(parent(k)).compareTo(data.get(k)) < 0;
}

從堆中取出元素和Sift Down

從堆的定義的第二條中是牢，任何節(jié)點(diǎn)的值都大于等于（或小于等于）子樹(shù)節(jié)點(diǎn)的值，我們可以發(fā)現(xiàn)陕截，堆頂元素存儲(chǔ)的就是堆中數(shù)據(jù)的最大值或者最小值驳棱。

而從堆中取出元素其實(shí)就是取出堆中最大或最小的元素，并且取出后會(huì)刪除农曲，所以也可以理解為刪除堆頂元素社搅。堆頂也就是堆的根節(jié)點(diǎn)，或者說(shuō)是數(shù)組下標(biāo)為0或1的元素乳规。

假設(shè)我們構(gòu)造的是大頂堆形葬，堆頂元素就是最大的元素。當(dāng)我們刪除堆頂元素之后暮的，就需要把最后一個(gè)節(jié)點(diǎn)放到堆頂笙以，然后利用同樣的父子節(jié)點(diǎn)對(duì)比方法。對(duì)于不滿足父子節(jié)點(diǎn)大小關(guān)系的冻辩，互換兩個(gè)節(jié)點(diǎn)猖腕，并且重復(fù)進(jìn)行這個(gè)過(guò)程，直到父子節(jié)點(diǎn)之間滿足大小關(guān)系為止微猖。這就是從上往下（Sift Down）的堆化方法谈息。如下圖：

image.png

因?yàn)槲覀円瞥氖菙?shù)組中的最后一個(gè)元素缘屹，而在堆化的過(guò)程中凛剥，都是交換操作，不會(huì)出現(xiàn)數(shù)組中的“空洞”轻姿，所以這種方法堆化之后的結(jié)果犁珠，肯定滿足完全二叉樹(shù)的特性逻炊。

具體的實(shí)現(xiàn)代碼如下：

/**
 * 獲取堆頂元素
 */
public E findMax() {
    if (isEmpty()) {
        throw new IllegalArgumentException("Can't find max when heap is empty.");
    }

    return data.get(0);
}

/**
 * 從堆中取出元素，也就是取出堆頂元素
 */
public E extractMax() {
    E ret = findMax();
    // 交換根節(jié)點(diǎn)與最后一個(gè)節(jié)點(diǎn)的位置
    Collections.swap(data, 0, data.size() - 1);
    // 刪除最后一個(gè)節(jié)點(diǎn)
    data.remove(data.size() - 1);
    siftDown(0);

    return ret;
}

/**
 * 從上往下調(diào)整元素的位置犁享，直到元素到達(dá)葉子節(jié)點(diǎn)或大于左右子節(jié)點(diǎn)
 */
private void siftDown(int k) {
    // 左子節(jié)點(diǎn)大于size時(shí)就證明到底了
    while (leftChild(k) < data.size()) {
        int leftChildIndex = leftChild(k);
        int rightChildIndex = leftChildIndex + 1;
        int maxChildIndex = leftChildIndex;

        // 左右子節(jié)點(diǎn)中最大的節(jié)點(diǎn)下標(biāo)
        if (rightChildIndex < data.size() &&
                isGreaterThan(rightChildIndex, leftChildIndex)) {
            maxChildIndex = rightChildIndex;
        }

        // 大于最大的子節(jié)點(diǎn)證明 k 已經(jīng)大于左右子節(jié)點(diǎn)余素，無(wú)需再繼續(xù)下沉了
        if (data.get(k).compareTo(data.get(maxChildIndex)) >= 0) {
            break;
        }

        // 否則，交換 k 與其最大子節(jié)點(diǎn)的位置炊昆，繼續(xù)下沉
        Collections.swap(data, k, maxChildIndex);
        k = maxChildIndex;
    }
}

/**
 * 判斷右子節(jié)點(diǎn)是否大于左子節(jié)點(diǎn)
 */
private boolean isGreaterThan(int rightChildIndex, int leftChildIndex) {
    return data.get(rightChildIndex).compareTo(data.get(leftChildIndex)) > 0;
}

到此為止桨吊，我們就已經(jīng)實(shí)現(xiàn)了堆的核心操作。接下來(lái)我們使用一個(gè)簡(jiǎn)單的測(cè)試用例凤巨，測(cè)試下這個(gè)堆的行為是否符合預(yù)期视乐。測(cè)試代碼如下：

/**
 * 測(cè)試堆的行為是否符合預(yù)期
 */
private static void testAddAndExtractMax() {
    int n = 1000000;
    // 隨機(jī)往堆里添加n個(gè)元素
    MaxHeap<Integer> maxHeap = new MaxHeap<>();
    Random random = new Random();
    for (int i = 0; i < n; i++) {
        maxHeap.add(random.nextInt(Integer.MAX_VALUE));
    }

    // 取出堆中的所有元素，放到arr中
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = maxHeap.extractMax();
    }

    // 由于堆的特性敢茁，此時(shí)arr中的元素理應(yīng)是有序的
    // 所以這里校驗(yàn)一下arr是否是有序的佑淀，如果無(wú)序則代表堆的實(shí)現(xiàn)有問(wèn)題
    for (int i = 1; i < n; i++) {
        if (arr[i - 1] < arr[i]) {
            throw new IllegalArgumentException("Error");
        }
    }

    System.out.println("Test MaxHeap completed.");
}

public static void main(String[] args) {
    testAddAndExtractMax();
}

Heapify 和 Replace

堆的 Heapify 和 Replace 也是比較常見(jiàn)的操作，雖然使用之前所編寫的代碼也能實(shí)現(xiàn)彰檬，但并不是那么好使伸刃，例如實(shí)現(xiàn) Replace 需要兩次的操作。所以在本小節(jié)就為這兩個(gè)操作逢倍，單獨(dú)編寫相應(yīng)的代碼捧颅。

Replace

• Replace：取出最大元素后，放入一個(gè)新元素
• 使用已有代碼的實(shí)現(xiàn)：可以先extractMax较雕，再add隘道，兩次的操作
• 新的實(shí)現(xiàn)：可以直接將堆頂元素替換以后進(jìn)行Sift Down，只需要一次的操作

有了之前的代碼基礎(chǔ)郎笆，實(shí)現(xiàn) Replace 就非常簡(jiǎn)單了谭梗，只需要幾行代碼。如下：

/**
 * 取出堆中的最大元素宛蚓，并且替換成元素e
 */
public E replace(E e) {
    E ret = findMax();
    // 替換堆頂元素
    data.set(0, e);
    siftDown(0);

    return ret;
}

Heapify

• Heapify：將任意數(shù)組整理成堆的形狀激捏，也就是對(duì)一個(gè)數(shù)組進(jìn)行堆化，或者說(shuō)是建堆
• 使用已有代碼的實(shí)現(xiàn)：遍歷數(shù)組凄吏，調(diào)用add將每個(gè)元素添加到堆里远舅。時(shí)間復(fù)雜度是
• 新的實(shí)現(xiàn)：從后往前處理數(shù)組，并且每個(gè)數(shù)據(jù)都是從上往下堆化痕钢。因?yàn)槿~子節(jié)點(diǎn)往下堆化只能自己跟自己比較图柏，所以我們直接從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，依次堆化就行了任连。這樣相當(dāng)于只需要對(duì)數(shù)組中一半的元素進(jìn)行Sift Down操作蚤吹。時(shí)間復(fù)雜度是

建堆的分解步驟圖如下：

image.png

image.png

同樣，基于之前已有的代碼，Heapify 實(shí)現(xiàn)起來(lái)也非常的簡(jiǎn)單裁着，我們可以選擇在構(gòu)造器中提供這個(gè)功能繁涂。具體的實(shí)現(xiàn)代碼如下：

public MaxHeap(E[] arr) {
    this.data = asArrayList(arr);
    // 最后一個(gè)非葉子節(jié)點(diǎn)的下標(biāo)
    int lastNode = parent(data.size() - 1);
    for (int i = lastNode; i >= 0; i--) {
        // 從后往前依次堆化
        siftDown(i);
    }
}

/**
 * 將數(shù)組轉(zhuǎn)換為ArrayList
 */
private ArrayList<E> asArrayList(E[] arr) {
    ArrayList<E> ret = new ArrayList<>();
    Collections.addAll(ret, arr);

    return ret;
}

基于堆的優(yōu)先隊(duì)列

現(xiàn)在我們已經(jīng)了解了優(yōu)先隊(duì)列和堆，并且自己動(dòng)手實(shí)現(xiàn)了一個(gè)堆二驰，因此扔罪，不難看得出來(lái)，堆和優(yōu)先隊(duì)列非常相似桶雀。一個(gè)堆其實(shí)就可以看作是一個(gè)優(yōu)先隊(duì)列矿酵。Java中的優(yōu)先隊(duì)列也是基于堆實(shí)現(xiàn)的，是一個(gè)小頂堆矗积。

很多時(shí)候坏瘩，它們只是概念上的區(qū)分而已。往優(yōu)先隊(duì)列中插入一個(gè)元素漠魏，就相當(dāng)于往堆中插入一個(gè)元素倔矾；從優(yōu)先隊(duì)列中取出優(yōu)先級(jí)最高的元素，就相當(dāng)于取出堆頂元素柱锹。所以哪自，堆和優(yōu)先隊(duì)列在基本行為上是等價(jià)的。

我們之前也提到了優(yōu)先隊(duì)列可以使用不同的方式進(jìn)行實(shí)現(xiàn)禁熏，但使用堆這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列是最高效也最符合直覺(jué)的壤巷，因?yàn)槎驯旧砭褪且粋€(gè)優(yōu)先隊(duì)列。

從下圖中可以看到使用不同數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先隊(duì)列的時(shí)間復(fù)雜度：

image.png

接下來(lái)瞧毙，我們就實(shí)現(xiàn)一個(gè)基于堆的優(yōu)先隊(duì)列胧华。首先，定義一個(gè)隊(duì)列接口：

package queue;

/**
 * 隊(duì)列數(shù)據(jù)結(jié)構(gòu)接口
 *
 * @author 01
 **/
public interface Queue<E> {
    /**
     * 新元素入隊(duì)
     *
     * @param e 新元素
     */
    void enqueue(E e);

    /**
     * 元素出隊(duì)
     *
     * @return 元素
     */
    E dequeue();

    /**
     * 獲取位于隊(duì)首的元素
     *
     * @return 隊(duì)首的元素
     */
    E getFront();

    /**
     * 獲取隊(duì)列中的元素個(gè)數(shù)
     *
     * @return 元素個(gè)數(shù)
     */
    int getSize();

    /**
     * 隊(duì)列是否為空
     *
     * @return 為空返回true宙彪，否則返回false
     */
    boolean isEmpty();
}

然后實(shí)現(xiàn)接口中的方法矩动，由于我們之前已經(jīng)實(shí)現(xiàn)了一個(gè)堆，所以這個(gè)優(yōu)先隊(duì)列實(shí)現(xiàn)起來(lái)就非常簡(jiǎn)單了：

package queue;

import heap.MaxHeap;

/**
 * 基于堆實(shí)現(xiàn)的優(yōu)先隊(duì)列
 *
 * @author 01
 * @date 2021-01-19
 */
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private final MaxHeap<E> maxHeap;

    public PriorityQueue() {
        maxHeap = new MaxHeap<>();
    }

    @Override
    public int getSize() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }
}