av在线人妻,玖玖爱在线视频免费看

什么是優(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ù)，持有金卡的客戶(hù)可以?xún)?yōu)先于普通卡的客戶(hù)被接待，而鉆石卡的客戶(hù)又優(yōu)先于金卡的客戶(hù)，以此類(lèi)推。這就是一種優(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)要求，只要滿(mǎ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ù)都是滿(mǎn)的，最后一層的節(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)為 $i$ 的節(jié)點(diǎn)的左子節(jié)點(diǎn)，就是下標(biāo)為 $2?i$ 的節(jié)點(diǎn)，右子節(jié)點(diǎn)則是下標(biāo)為 $2?i+1$ 的節(jié)點(diǎn)。所以反過(guò)來(lái)，其父節(jié)點(diǎn)也就是下標(biāo)為 $\frac{i}{2}?$ 的節(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)是 $i$ ，那左子節(jié)點(diǎn)的下標(biāo)就是 $2?i+1$ ，右子節(jié)點(diǎn)的下標(biāo)就是 $2?i+2$ ，父節(jié)點(diǎn)的下標(biāo)就是 $\frac{i-1}{2}?$ ?。如下圖所示：

image.png

有了以上的認(rèn)知后，接下來(lái)，我們就可以先編寫(xiě)一個(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ù)滿(mǎn)足堆的兩個(gè)特性。如果我們把新添加的元素放到數(shù)組的最后，如下圖，是不是就不符合堆的特性了？

image.png

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

看下面這張使用Sift Up方式的堆化過(guò)程分解圖。我們可以讓新插入的節(jié)點(diǎn)與父節(jié)點(diǎn)對(duì)比大小。如果不滿(mǎn)足子節(jié)點(diǎn)小于等于父節(jié)點(diǎn)的大小關(guān)系，我們就互換兩個(gè)節(jié)點(diǎn)。一直重復(fù)這個(gè)過(guò)程，直到父子節(jié)點(diǎn)之間滿(mǎ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ì)于不滿(mǎn)足父子節(jié)點(diǎn)大小關(guān)系的，互換兩個(gè)節(jié)點(diǎn)，并且重復(fù)進(jìn)行這個(gè)過(guò)程，直到父子節(jié)點(diǎn)之間滿(mǎn)足大小關(guān)系為止。這就是從上往下（Sift Down）的堆化方法。如下圖：

image.png

因?yàn)槲覀円瞥氖菙?shù)組中的最后一個(gè)元素，而在堆化的過(guò)程中，都是交換操作，不會(huì)出現(xiàn)數(shù)組中的“空洞”，所以這種方法堆化之后的結(jié)果，肯定滿(mǎn)足完全二叉樹(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)的操作，雖然使用之前所編寫(xiě)的代碼也能實(shí)現(xiàn)，但并不是那么好使，例如實(shí)現(xiàn) Replace 需要兩次 $O(logn)$ 的操作。所以在本小節(jié)就為這兩個(gè)操作，單獨(dú)編寫(xiě)相應(yīng)的代碼。

Replace

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

有了之前的代碼基礎(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ù)雜度是 $O(nlogn)$
新的實(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ù)雜度是 $O(n)$

建堆的分解步驟圖如下：

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)之優(yōu)先隊(duì)列和堆

數(shù)據(jù)結(jié)構(gòu)之優(yōu)先隊(duì)列和堆

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

堆的基礎(chǔ)表示

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

向堆中添加元素和Sift Up

從堆中取出元素和Sift Down

Heapify 和 Replace

Replace

Heapify

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)之優(yōu)先隊(duì)列和堆

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

堆的基礎(chǔ)表示

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

向堆中添加元素和Sift Up

從堆中取出元素和Sift Down

Heapify 和 Replace

Replace

Heapify

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

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av