圖解堆結(jié)構(gòu)、堆排序及堆的應(yīng)用

前言

上一次我們介紹了選擇類排序中的簡單選擇排序，簡單歸簡單，但是時間復(fù)雜度是O(n^2)，這次我們介紹另一種時間復(fù)雜度為O(nlogn)的選擇類排序方法叫做堆排序。

我將從以下幾個方面介紹：

  • 堆的結(jié)構(gòu)
  • 堆排序
  • 優(yōu)化的堆排序
  • 原地堆排序
  • 堆的應(yīng)用

堆的結(jié)構(gòu)

什么是堆？我給出了百度的定義，如下：

堆(Heap)是計算機科學中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。堆通常是一個可以被看做一棵完全二叉樹的數(shù)組對象。

堆總是滿足下列性質(zhì)：

  • 堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值。
  • 堆總是一棵完全二叉樹。

將根節(jié)點最大的堆叫做最大堆，根節(jié)點最小的堆叫做最小堆。

下圖展示了一個最大堆的結(jié)構(gòu)：

image

可見，堆中某個節(jié)點的值總是小于等于其父節(jié)點的值。

由于堆是一棵完全二叉樹，因此我們可以對每一層進行編號，如下：

image

我們完全可以使用數(shù)組存放這些元素，那如何確定存放的位置呢？利用如下公式：

父節(jié)點：parent(i) = (i-1)/2

左孩子：leftChild(i) = 2i+1*

右孩子：rightChild(i) = 2i+2*

相關(guān)代碼如下：

private int parent(int index) {
    return (index - 1) / 2;
}

private int leftChild(int index) {
    return index * 2 + 1;
}

private int rightChild(int index) {
    return index * 2 + 2;
}

添加元素

向堆中添加元素的步驟如下：

  1. 將新元素放到數(shù)組的末尾。
  2. 獲取新元素的父親節(jié)點在數(shù)組中的位置，比較新元素和父親節(jié)點的值，如果父親節(jié)點的值小于新元素的值，那么兩者交換。以此類推，不斷向上比較，直到根節(jié)點結(jié)束。

下圖展示了添加元素的過程：

image

添加元素的過程也叫做siftUp，代碼如下：

// Array是自己實現(xiàn)的動態(tài)數(shù)組
private Array<E> data;

public void add(E e) {
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k) {
    while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
        data.swap(k, parent(k));
        k = parent(k);
    }
}

刪除元素

刪除元素其實就是刪除堆頂?shù)脑?，步驟如下：

  1. 讓數(shù)組最后一個元素和數(shù)組第一個元素（堆頂元素）交換。
  2. 交換完后，刪除數(shù)組最后的元素。
  3. 讓堆頂元素和左右孩子節(jié)點比較，如果堆頂元素比左右孩子節(jié)點中最大的元素還要大，那么滿足堆的性質(zhì)，直接退出。否則如果堆頂元素比左右孩子節(jié)點中最大的元素小，那么堆頂元素就和最大的元素交換，然后繼續(xù)重復(fù)執(zhí)行以上操作，只不過這時候把堆頂元素稱為父節(jié)點更好。

下圖展示了刪除元素的過程：

image

刪除元素的過程也叫做siftDown，代碼如下：

// 這里我們不命名為remove，命名為extractMax，抽取堆頂最大元素
public E extractMax() {
    E ret = findMax();
    // 讓最后一個葉子節(jié)點補到根節(jié)點，然后讓它下沉
    // (為什么是取最后一個葉子節(jié)點，因為即使取走最后一個葉子節(jié)點，依舊能保持是一棵完全二叉樹)
    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);
    return ret;
}

private void siftDown(int k) {
    while (leftChild(k) < data.getSize()) {
        int j = leftChild(k);
        if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
            j = rightChild(k);
            // data[j]是leftChild和rightChild中的最大值
        }

        // 如果父節(jié)點比左右孩子中的最大值還要大，那么說明沒有問題，直接退出
        if (data.get(k).compareTo(data.get(j)) >= 0) {
            break;
        }
        // 否則交換
        data.swap(k, j);
        k = j;
    }
}

最大堆的完整代碼

堆排序

通過上面的介紹，我們應(yīng)該明白了堆的結(jié)構(gòu)，堆的添加和刪除元素操作是如何完成的。那么對于堆排序來說，就是小菜一碟了，因為堆排序就是用到了堆的添加和刪除操作，步驟如下：

  1. 將數(shù)組中元素一個個添加到堆（最大堆）中。
  2. 添加完成后，每次取出一個元素倒序放入到數(shù)組中。

堆排序代碼：

public static void sort(Comparable[] arr) {
    int n = arr.length;
    // MaxHeap是自己實現(xiàn)的最大堆
    MaxHeap<Comparable> maxHeap = new MaxHeap<>(n);
    for (int i = 0; i < n; i++) {
        maxHeap.add(arr[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax();
    }
}

堆排序完整代碼

優(yōu)化的堆排序

在上述的堆排序中，我們在將數(shù)組中元素添加到堆時，都是一個個添加，是否有優(yōu)化的方法呢？答案是有的，我們可以將數(shù)組直接轉(zhuǎn)換成堆，這種操作叫做Heapify。

Heapify就是從最后一個節(jié)點開始，判斷父節(jié)點是否比孩子節(jié)點大，不是就siftDown。Heapify操作的時間復(fù)雜度是O(n)，相比一個個添加的時間復(fù)雜度是O(nlogn)，可見性能提升了不少。

假設(shè)我們有數(shù)組：[15, 18, 12, 16, 22, 28, 16, 45, 30, 52]，下圖展示了對其進行Heapify的過程。

image

優(yōu)化的堆排序代碼：

public static void sort(Comparable[] arr) {
    int n = arr.length;
    // MaxHeap是自己實現(xiàn)的最大堆，當傳入數(shù)組作為構(gòu)造參數(shù)時，會對其進行heapify
    MaxHeap<Comparable> maxHeap = new MaxHeap<>(arr);
    for (int i = n - 1; i >= 0; i--) {
        arr[i] = maxHeap.extractMax();
    }
}

// 構(gòu)造方法
public MaxHeap(E[] arr) {
    data = new Array<>(arr);
    // 將數(shù)組堆化的過程就是從最后一個節(jié)點開始，判斷父節(jié)點是否比子節(jié)點大，不是就siftDown
    for (int i = parent(arr.length - 1); i >= 0; i--) {
        siftDown(i);
    }
}

優(yōu)化的堆排序完整代碼

原地堆排序

原地堆排序可以讓我們的空間復(fù)雜度變?yōu)?code>O(1)，因為不占用新的數(shù)組。

原地堆排序類似于堆的刪除元素，步驟如下：

  1. 對數(shù)組Heapify。
  2. 我們讓數(shù)組最后一個元素和第一個元素交換，這時數(shù)組最后一個元素就是最大的。
  3. 然后讓數(shù)組第一個元素siftDown，這樣除去最后一個元素，前面又是一個最大堆。
  4. 我們讓數(shù)組倒數(shù)第二個元素和第一個元素交換，這時數(shù)組倒數(shù)第二個元素就是次最大的。
  5. 然后讓數(shù)組第一個元素siftDown，這樣除去最后一個元素和倒數(shù)第二個元素，前面又是一個最大堆。
  6. 以此類推，像這樣倒著排，即可完成從小到大的排序。

下圖展示了原地堆排序的過程：

image

原地堆排序代碼：

public static void sort(Comparable[] arr) {
    int n = arr.length;
    // heapify
    for (int i = parent(n-1); i >= 0; i--) {
        siftDown(arr, n, i);
    }

    // 核心代碼
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);
        siftDown(arr, i, 0);
    }
}

private static void swap(Object[] arr, int i, int j) {
    Object t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

private static void siftDown(Comparable[] arr, int n, int k) {

    while (leftChild(k) < n) {
        int j = leftChild(k);
        if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0) {
            j = rightChild(k);
        }

        // 如果父節(jié)點比左右孩子中的最大值還要大，那么說明沒有問題，直接退出
        if (arr[k].compareTo(arr[j]) >= 0) {
            break;
        }

        // 否則交換
        swap(arr, k, j);
        k = j;
    }
}

原地堆排序完整代碼

堆的應(yīng)用

優(yōu)先級隊列

一旦我們掌握了堆這個數(shù)據(jù)結(jié)構(gòu)，那么優(yōu)先級隊列的實現(xiàn)就很簡單了，只需要弄清楚優(yōu)先級隊列需要有哪些接口就行。JDK 中自帶的PriorityQueue就是用堆實現(xiàn)的優(yōu)先級隊列，不過需要注意PriorityQueue內(nèi)部使用的是最小堆。

優(yōu)先級隊列完整代碼

Top K 問題

Top K 問題就是求解前 K 個最大的元素或者最小的元素。元素個數(shù)不確定，數(shù)據(jù)量可能很大，甚至源源不斷到來，但需要知道目前為止前 K 個最大或最小的元素。當然問題還可能變?yōu)榍蠼?strong>第 K 個最大的元素或最小的元素。

通常我們有如下解決方案：

  1. 使用JDK中自帶的排序，如Arrays.sort()，由于底層使用的快速排序，所以時間復(fù)雜度為O(nlogn)。但是如果 K 取值很小，比如是 1，即取最大值，那么對所有元素排序就沒有必要了。
  2. 使用簡單選擇排序，選擇 K 次，那么時間復(fù)雜度為O(n*K)，如果 K 大于 logn，那還不如快排呢！

上述兩種思路都是假定所有元素已知，如果元素個數(shù)不確定，且數(shù)據(jù)源源不斷到來的話，就無能為力了。

下面提供一種新的思路：

我們維護一個長度為 K 的數(shù)組，最前面 K 個元素就是目前最大的 K 個元素，以后每來一個新元素，都先找數(shù)組中的最小值，將新元素與最小值相比，如果小于最小值，則什么都不變，如果大于最小值，則將最小值替換為新元素。這樣一來，數(shù)組中維護的永遠是最大的 K 個元素，不管數(shù)據(jù)源有多少，需要的內(nèi)存開銷都是固定的，就是長度為 K 的數(shù)組。不過，每來一個元素，都需要找到最小值，進行 K 次比較，是否有辦法能減少比較次數(shù)呢？

當然，這時候堆就要登場了，我們使用最小堆維護這 K 個元素，每次來新的元素，只需要和根節(jié)點比較，小于等于根節(jié)點，不需要變化，否則用新元素替換根節(jié)點，然后siftDown調(diào)整堆即可。此時的時間復(fù)雜度為O(nlogK)，相比上述兩種方法，效率大大提升，且空間復(fù)雜度也大大降低。

Top K 問題代碼：

public class TopK<E extends Comparable<E>> {

    private PriorityQueue<E> p;
    private int k;

    public TopK(int k) {
        this.k = k;
        this.p = new PriorityQueue<>(k);
    }

    public void addAll(Collection<? extends E> c) {
        for (E e : c) {
            add(e);
        }
    }

    public void add(E e) {
        // 未滿k個時，直接添加
        if (p.size() < k) {
            p.add(e);
            return;
        }

        E head = p.peek();
        if (head != null && head.compareTo(e) >= 0) {
            // 小于等于TopK中的最小值，不用變
            return;
        }
        // 否則，新元素替換原來的最小值
        p.poll();
        p.add(e);
    }

    /**
     * 獲取當前的最大的K個元素
     *
     * @param a   返回類型的空數(shù)組
     * @param <T>
     * @return TopK以數(shù)組形式
     */
    public E[] toArray(E[] a) {
        return p.toArray(a);
    }

    /**
     * 獲取第K個最大的元素
     *
     * @return 第K個最大的元素
     */
    public E getKth() {
        return p.peek();
    }

    public static void main(String[] args) {
        TopK<Integer> top5 = new TopK<>(5);
        top5.addAll(Arrays.asList(88, 1, 5, 7, 28, 12, 3, 22, 20, 70));
        System.out.println("top5：" + Arrays.toString(top5.toArray(new Integer[0])));
        System.out.println("5th：" + top5.getKth());
    }

}

這里我們直接利用 JDK 自帶的由最小堆實現(xiàn)的優(yōu)先級隊列PriorityQueue。

依此思路，可以實現(xiàn)求前 K 個最小元素，只需要在實例化PriorityQueue時傳入一個反向比較器參數(shù)，然后更改add方法的邏輯。

中位數(shù)

堆也可以用于求解中位數(shù)，數(shù)據(jù)量可能很大且源源不斷到來。

注意：如果元素個數(shù)是偶數(shù)，那么我們假定中位數(shù)取任意一個都可以。

有了上面的例子，這里就很好理解了。我們使用兩個堆，一個最大堆，一個最小堆，步驟如下：

  1. 添加的第一個元素作為中位數(shù) m，最大堆維護 <= m 的元素，最小堆維護 >= m 的元素，兩個堆都不包含 m。
  2. 當添加第二個元素 e 時，將 e 與 m 比較，若 e <= m，則將其加入到最大堆中，否則加入到最小堆中。
  3. 如果出現(xiàn)最小堆和最大堆的元素個數(shù)相差 >= 2，則將 m 加入元素個數(shù)少的堆中，然后讓元素個數(shù)多的堆將根節(jié)點移除并賦值給 m。
  4. 以此類推不斷更新。

假設(shè)有數(shù)組[20, 30, 40, 50, 2, 4, 3, 5, 7, 8, 10]。

下圖展示了整個操作的過程：

image

求解中位數(shù)的代碼：

public class Median<E extends Comparable<E>> {

    /**
     * 最小堆
     */
    private PriorityQueue<E> minP;

    /**
     * 最大堆
     */
    private PriorityQueue<E> maxP;

    /**
     * 當前中位數(shù)
     */
    private E m;

    public Median() {
        this.minP = new PriorityQueue<>();
        this.maxP = new PriorityQueue<>(11, Collections.reverseOrder());
    }

    private int compare(E e, E m) {
        return e.compareTo(m);
    }

    public void addAll(Collection<? extends E> c) {
        for (E e : c) {
            add(e);
        }
    }

    public void add(E e) {
        // 第一個元素
        if (m == null) {
            m = e;
            return;
        }

        if (compare(e, m) <= 0) {
            // 小于等于中值，加入最大堆
            maxP.add(e);
        } else {
            // 大于中值，加入最大堆
            minP.add(e);
        }

        if (minP.size() - maxP.size() >= 2) {
            // 最小堆元素個數(shù)多，即大于中值的數(shù)多
            // 將 m 加入到最大堆中，然后將最小堆中的根移除賦給 m
            maxP.add(m);
            m = minP.poll();
        } else if (maxP.size() - minP.size() >= 2) {
            minP.add(m);
            m = maxP.poll();
        }

    }

    public E getMedian() {
        return m;
    }

    public static void main(String[] args) {
        Median<Integer> median = new Median<>();
        median.addAll(Arrays.asList(20, 30, 40, 50, 2, 4, 3, 5, 7, 8, 10));
        System.out.println(median.getMedian());
    }
}
image
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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

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