點贊關(guān)注，不再迷路，你的支持對我意義重大！

?? Hi，我是丑丑。本文「數(shù)據(jù)結(jié)構(gòu) & 算法」| 導(dǎo)讀 —— 登高博見已收錄，這里有 Android 進階成長路線筆記 & 博客，歡迎跟著彭丑丑一起成長。（聯(lián)系方式在 GitHub）

前言

今天，我們來討論一個非常實用的數(shù)據(jù)結(jié)構(gòu)——二叉堆（Binary Heap，簡稱：堆），它最主要的應(yīng)用場景有 堆排序 & 優(yōu)先隊列 & Top K & 最大索引堆。與堆相關(guān)算法題目基本屬于中等難度，在算法面試中也比較常見，建議應(yīng)試者著重學(xué)習(xí)；
在這篇文章里，我將梳理堆的 基本知識 & 常考題型。如果能幫上忙，請務(wù)必點贊加關(guān)注，這真的對我非常重要。

1. 基本概念

邏輯結(jié)構(gòu)

二叉堆（Binary Heap） 是一種特殊的完全二叉樹，即：每個節(jié)點都大于等于（或者小于等于）子節(jié)點。需要注意的是，兄弟節(jié)點的相對大小是不重要的。

具體來說，如果每個節(jié)點都大于等于子節(jié)點，這種堆稱為 大頂堆 / 最大堆；如果每個節(jié)點都小于等于子節(jié)點，這種堆稱為 小頂堆 / 最小堆。

物理結(jié)構(gòu)

樹可以采用數(shù)組 & 鏈表兩種存儲方式，對于二叉堆（完全二叉樹）來說，數(shù)組存儲方式是空間利用率最高的存儲方式。因此通常來說，二叉堆是基于數(shù)組的數(shù)據(jù)結(jié)構(gòu)。

2. 堆的基本操作

這一節(jié)，我們先來討論堆的三個基本操作 —— 上浮 & 下沉 & 建堆，這三個操作的目的其實都是堆化（Heapify）。建堆的作用是把一組數(shù)據(jù)轉(zhuǎn)換為滿足堆性質(zhì)的數(shù)據(jù)結(jié)構(gòu)，而上浮和下沉的作用是在堆結(jié)構(gòu)變化之后，適當?shù)卣{(diào)整節(jié)點使其重新滿足堆的性質(zhì) 。

提示： 為了專注于討論二叉堆的相關(guān)內(nèi)容，在這一節(jié)里我們不考慮泛型，同時以大頂堆為例子。

2.1 上?。ㄌ砑釉兀?/h2>

往堆里添加元素時，需要執(zhí)行上浮操作，具體步驟如下：

1、新元素放在數(shù)組末尾（注意：是有效數(shù)據(jù)的末尾，而不是數(shù)組物理區(qū)域的末尾）；
2、與父節(jié)點比較，如果不滿足堆的性質(zhì)，則交換父子節(jié)點；
3、重復(fù)步驟 2，直到滿足堆的性質(zhì)。

提示： 從數(shù)組末尾開始上浮，數(shù)組交換和一定的次數(shù)最少。

引用自 https://time.geekbang.org/column/article/69913 —— 王爭著

結(jié)合代碼可能更容易理解：

根節(jié)點存儲在第 [0] 位

public class Heap {

    private Integer[] data;
    private int count;

    添加元素
    private void insert(Integer x) {
        int i = count;
        data[count++] = x;
        siftup(i);
    }

    上浮操作
    private void siftup(int k) {
        while (k > 0 && data[(k - 1) / 2] < data[k]) {
            swap(data, (k - 1) / 2, k);
            k /= 2;
        }
    }
}

這段代碼存在著一些不必要的賦值操作，可以優(yōu)化，優(yōu)化后目標元素只會賦值一次到最終位置：

參考 JDK 1.5 java.util.PriorityQueue.java

添加元素
private void insert(Integerx) {
    int i = count;
    data[count++] = x;
    siftup(i, x);
}

上浮操作
private void siftup(int k, Integer x) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Integer parentE = data[parent];
        if (parentE >= x)
            break;
        data[k] = parentE;
        k = parent;
    }
    data[k] = x;
}

2.2 下沉（取出元素）

往堆里取出元素時，需要執(zhí)行下沉操作，具體步驟如下：

1、取出堆頂元素，即數(shù)組第 1 個元素（索引為 0 或 1，取決于具體實現(xiàn)）；
2、數(shù)組最后一個元素放到數(shù)組 1 個元素的位置；
3、與子節(jié)點比較，如果不滿足堆的性質(zhì)，則交換父節(jié)點與子節(jié)點中最小的那個；
4、重復(fù)步驟 3，直到滿足堆的性質(zhì)。

提示： 從數(shù)組頭部開始下沉，數(shù)組交換和一定的次數(shù)最少，同時能夠避免出現(xiàn) 數(shù)組空洞。

引用自 https://time.geekbang.org/column/article/69913 —— 王爭著

另外，需要注意到葉子節(jié)點是沒有子節(jié)點的，不需要執(zhí)行下沉操作，可以提前結(jié)束。（根節(jié)點存儲在第 [0] 位時，葉子節(jié)點下標為 $\frac{count} {2} 到 count-1$ ，根節(jié)點存儲在第 [1] 位時，葉子節(jié)點下標為 $\frac{count}{2} + 1 到 count$ ）。

結(jié)合代碼可能更容易理解：

根節(jié)點存儲在第 [0] 位

public class Heap {

    private Integer[] data;
    private int count;

    取出堆頂元素
    int poll() {
        int k = --count;
        int result = data[0];
        int x = data[k];
        data[k] = null;
        if (k != 0) {
            siftdownV2(0);
        }
        return result;
    }
    
    下沉操作
    void siftdown(int k) {
        int half = count / 2;
        while (k < half) {
            int minPos = k;
            if (data[k * 2 + 1] < data[k]) minPos = k * 2 + 1;
            if (data[k * 2 + 2] < count && data[k * 2 + 2] < data[k]) minPos = k * 2 + 2;
            if (minPos == k)
                break;
            swap(data, k, minPos);
            k = minPos;
        }
    }
}

這段代碼存在著一些不必要的賦值操作，可以優(yōu)化，優(yōu)化后目標元素只會賦值一次到最終位置：
參考 JDK 1.5 java.util.PriorityQueue.java

取出堆頂元素
private int poll() {
    int k = --count;
    int result = data[0];
    int x = data[k];
    data[k] = null;
    if (k != 0) {
        siftdown(0, x);
    }
    return result;
}

下沉操作
private void siftdown(int k, int x) {
    注意：葉子節(jié)點沒有子節(jié)點，不需要下沉
    int half = count >>> 1;
    while (k < half) {
    int child = (k << 1) + 1; // assume left child is least
    Integer childE = data[child];
    int right = child + 1;
    if (right < count && childE > data[right])
        childE = data[child = right];
        if (x < childE)
            break;
        data[k] = childE;
        k = child;
    }
    data[k] = x;
}

2.3 建堆

前面講的上浮和下沉操作的前提是數(shù)組本身是堆化的，那么這一節(jié)我們就來討論建堆這一操作。

建堆可以分為 原地建堆 & 非原地建堆，原地建堆指的是將一個數(shù)組原地堆化的過程，而非原地建堆指的是輸入數(shù)據(jù)一個個添加到數(shù)組中的過程。可以觀察到，非原地建堆其實就是不斷添加元素執(zhí)行下沉操作的過程，等同于 第 2.1 節(jié) 上浮操作，所以我們主要是分析原地建堆。

原地建堆可以用兩種方法實現(xiàn)，分別為 從下往上堆化 & 從上往下堆化 ：

從下往上堆化

這種方法先將下標為 0 的第一個元素視為大小為 1 的堆，隨后將下標從 $1到count -1$ 的元素依次執(zhí)行上浮操作。這個過程也相當于不斷向這個初始大小為 1 的堆里添加元素。

從上往下堆化

這種方法先將葉子節(jié)點視為大小為 1 的堆，隨后將下標從 $\frac{count}{2}-1遞減到0$ 的節(jié)點執(zhí)行下沉操作。

2.4 復(fù)雜度分析

時間復(fù)雜度
- 上浮 & 下沉：沿著樹根節(jié)點到葉子節(jié)點的路徑進行比較和交換。而一個包含 n 個節(jié)點的二叉樹，樹的高度為 $lgn$ ，所以時間復(fù)雜度為 $O(lgn)$ ；
- 建堆：建堆的時間復(fù)雜度是 $O(n)$ ，推導(dǎo)過程可以看參考資料，這個結(jié)論還是比較重要的。
空間復(fù)雜度
堆化的過程中只是用了常量級變量，因此空間復(fù)雜度為 $O(1)$ 。

3. 堆的應(yīng)用 —— 堆排序

堆排序（Heap Sort） 指的是借助二叉堆實現(xiàn)的原地排序算法，它是一種時間復(fù)雜度為 $O(nlgn)$ 的不穩(wěn)定的排序算法，快速排序有幾分相似之處，后文我也會分析它們之間的區(qū)別。

總的來說，堆排序的過程可以分為 建堆 & 排序 兩個步驟：

3.1 建堆

建堆的過程在 第 2.3 節(jié)討論過了，假設(shè)我們要進行遞增排序的話，我們就需要建立一個大頂堆（每個節(jié)點都大于等于子節(jié)點）。

特別提示： 完成建堆后，數(shù)據(jù)處于 堆有序 狀態(tài)，但不是有序狀態(tài)，堆有序其實只是指數(shù)據(jù)滿足堆的性質(zhì)（每個節(jié)點都大于等于或小于等于子節(jié)點）。

3.2 排序

建立大頂堆后，現(xiàn)在我們來進行排序操作，具體操作如下：

1、堆頂元素，交換到數(shù)組末尾位置，此時，最大的元素已經(jīng)完成排序；
2、執(zhí)行下沉操作，將數(shù)組前 n - 1 個數(shù)據(jù)重新堆化；
3、重復(fù)步驟 1 和步驟 2，直到堆的大小為 1。

整個過程相當于執(zhí)行 n 次取出堆頂元素的操作，直到最后堆的大小為 1 時，數(shù)組完成排序。

引用自 https://time.geekbang.org/column/article/69913 —— 王爭著

3.3 復(fù)雜度分析

時間復(fù)雜度

下沉操作的時間復(fù)雜度是 $O(lgn)$ ，總共執(zhí)行 n 次，因此總體的時間復(fù)雜度為 $O(nlgn)$ ；

空間復(fù)雜度

堆排序是原地排序，建堆和排序的過程中只是用了常量級變量，因此總體的空間復(fù)雜度為 $O(1)$ 。

3.4 堆排序與快速排序?qū)Ρ?/h2>
前面提到了堆排序和快速排序的相似之處，那么兩者有何不同的？

數(shù)據(jù)訪問方式不同

快速排序是從數(shù)組下標依次遞增訪問數(shù)據(jù)，而堆排序是跳著訪問的，后者更不利于命中 CPU 緩存行。

數(shù)據(jù)交換次數(shù)不同

堆排序進行堆化時，可能會改變數(shù)據(jù)原本的相對順序，將原本相對有序的數(shù)組變得更加無序。這反而增加了逆序度，增加了執(zhí)行交換操作的次數(shù)。

考慮到這兩個因素，我們不難理解為什么 JDK 的 `java.util.Arrays.sort()`會選擇使用快速排序，而不是堆排序了。

當然了，堆排序也不是完全沒有價值，有一種場景堆排序就 “秒殺” 快速排序。那就是只需要取得前 k 個有序的數(shù)據(jù)時，即 Top k 問題，使用堆排序（或者稱為大小為 k 優(yōu)先隊列），時間復(fù)雜度僅為 $O(nlgk)$ 。

4. 堆的應(yīng)用 —— 優(yōu)先隊列

與優(yōu)先對列相似的有一種數(shù)據(jù)結(jié)構(gòu)：隊列，雖然它們的名稱很相似，但是本質(zhì)上區(qū)別是很大的：

數(shù)據(jù)結(jié)構(gòu)	描述
隊列	先進先出（FIFO），出隊順序由時間順序決定
優(yōu)先隊列	出隊順序與入隊順序無關(guān)，而由優(yōu)先級順序決定

4.1 優(yōu)先隊列的實現(xiàn)

狹義上，優(yōu)先隊列指的是基于二叉堆實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。而廣義上，凡是能夠?qū)崿F(xiàn)按優(yōu)先級順序出隊的數(shù)據(jù)結(jié)構(gòu)都可以稱為優(yōu)先隊列（例如 Android 領(lǐng)域熟知的 MessageQueue）。

提示： 當你看到優(yōu)先隊列這個詞的時候，如果沒有特殊上下文語境，指的就是基于堆實現(xiàn)的優(yōu)先隊列。

一般來說，優(yōu)先隊列有以下三種實現(xiàn)：

底層實現(xiàn)	入隊	出隊	舉例
普通數(shù)組	$O(1)$	$O(n)$ （掃描整個數(shù)組選擇最高優(yōu)先級）	/
順序數(shù)組	$O(n)$ （入隊時維護順序，下標靠前優(yōu)先級越高）	$O(1)$ （取出數(shù)組下標為 0 的元素）	Android MessageQueue
堆	$O(lgn)$	$O(lgn)$	Java PriorityQueue

可以觀察到，基于堆的優(yōu)先隊列平衡了入隊與出隊的時間復(fù)雜度。

4.2 優(yōu)先隊列的優(yōu)點

使用優(yōu)先隊列可以實現(xiàn) 高性能的定時器。

假設(shè)我們有一個定時器 / 消息器，里面存儲是等待執(zhí)行的定時任務(wù)，最笨的方法是每隔一小段時間掃描整個任務(wù)列表，篩選出到達執(zhí)行時間的任務(wù)。這樣做有兩大弊端：

1、無效輪詢：任務(wù)的執(zhí)行時間可能還差很久，前面的掃描都是無效的；
2、掃描耗時：如果任務(wù)列表非常龐大，一趟掃描會非常耗時。

而如果使用優(yōu)先隊列，則可以規(guī)避這兩個弊端，即不需要輪詢，也不需要掃描整個任務(wù)列表。

需要做的是維護定時任務(wù)列表的執(zhí)行優(yōu)先順序，每次從優(yōu)先隊列中取出隊首的任務(wù)。然后計算該任務(wù)執(zhí)行時間與當前時間的差值，把這個差值作為等待時間，等待這個時間之后再回來執(zhí)行任務(wù)（如果等待過程中對任務(wù)列表進行操作，則需要提前喚醒）。

Android 領(lǐng)域的小伙伴應(yīng)該對 MessageQueue 優(yōu)先隊列有深刻理解。雖然它并不是一個基于堆的優(yōu)先隊列，但是思路是一致的：如果當前時間還未到達隊首消息的執(zhí)行時間，那么當前線程等待，而不是輪詢判斷。Android 領(lǐng)域的小伙伴可以看看之前我寫的這篇文章：《Android | 面試必問的 Handler，你確定不看看？》

5. 堆的應(yīng)用 —— Top K 問題

5.1 題目描述

347. 前 K 個高頻元素 Top K Frequent Elements 【我的題解】
17.14. 最小K個數(shù) Smallest K LCCI 【我的題解】

輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個數(shù)。例如，輸入4、5、1、6、2、7、3、8這8個數(shù)字，則最小的4個數(shù)字是1、2、3、4。

Top K 問題是一個超高頻的面試算法問題，難度屬于中等，它的解法有很多個，最笨的方法是先將整個數(shù)組執(zhí)行快速排序，再返回排序后前 k 個數(shù)，時間復(fù)雜度為 $O(nlgn)$ 。在這里我們主要講使用二叉堆的解法。

5.2 解法步驟

步驟分解如下：

1、將數(shù)組前 k 個數(shù)添加到堆，建立一個大小為 k 的大頂堆；
2、依次遍歷數(shù)組后續(xù)的數(shù)，如果該數(shù)比堆頂?shù)臄?shù)更小，則將堆頂元素彈出，而該數(shù)添加到堆中；
3、重復(fù)步驟 2，直到所有數(shù)據(jù)處理完畢，最終堆中元素就是最小的 k 個數(shù)。

可以發(fā)現(xiàn)基于二叉堆的思路是 使用大頂堆維護數(shù)據(jù)的最小的 k 個數(shù)，每次將一個數(shù)與堆頂元素比較。如果該數(shù)小于堆頂元素，說明堆頂元素不是最小 k 小個數(shù)，應(yīng)當從堆里彈出，而該數(shù)添加到堆里。

5.3 復(fù)雜度分析

時間復(fù)雜度

建堆的時間復(fù)雜度是 $O(k)$ ，而取堆頂元素和插入元素的時間復(fù)雜度為 $O(lgk)$ ，因此總的時間復(fù)雜度為 $O(nlnk)$ ，優(yōu)于快速排序 $O(nlgn)$ ；

空間復(fù)雜度

維護了一個大小為 k 的二叉堆，空間復(fù)雜度為 $O(k)$ 。

6. 最大索引堆

Editting...

參考資料

《二叉堆》 —— 維基百科
《堆》 —— LeetCode 出品
《二叉堆詳解實現(xiàn)優(yōu)先級隊列》 —— labuladong 著
《第 11 章》優(yōu)先隊列與堆 —— liweiwei 著
《劍指 Offer》最小的 k 個數(shù) —— 何海濤著
《堆和堆排序：為什么說堆排序沒有快速排序快？》 —— 王爭著，極客時間出品
《堆的應(yīng)用：如何快速獲取到Top 10最熱門的搜索關(guān)鍵詞？》 —— 王爭著，極客時間出品

創(chuàng)作不易，你的「三連」是丑丑最大的動力，我們下次見！

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

「數(shù)據(jù)結(jié)構(gòu)」 | 二叉堆

「數(shù)據(jù)結(jié)構(gòu)」 | 二叉堆

前言

目錄

1. 基本概念

2. 堆的基本操作

2.2 下沉（取出元素）

2.3 建堆

2.4 復(fù)雜度分析

3. 堆的應(yīng)用 —— 堆排序

3.1 建堆

3.2 排序

3.3 復(fù)雜度分析

4. 堆的應(yīng)用 —— 優(yōu)先隊列

4.1 優(yōu)先隊列的實現(xiàn)

4.2 優(yōu)先隊列的優(yōu)點

5. 堆的應(yīng)用 —— Top K 問題

5.1 題目描述

5.2 解法步驟

5.3 復(fù)雜度分析

6. 最大索引堆

參考資料

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

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

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

「數(shù)據(jù)結(jié)構(gòu)」 | 二叉堆

前言

目錄

1. 基本概念

2. 堆的基本操作

2.2 下沉（取出元素）

2.3 建堆

2.4 復(fù)雜度分析

3. 堆的應(yīng)用 —— 堆排序

3.1 建堆

3.2 排序

3.3 復(fù)雜度分析

4. 堆的應(yīng)用 —— 優(yōu)先隊列

4.1 優(yōu)先隊列的實現(xiàn)

4.2 優(yōu)先隊列的優(yōu)點

5. 堆的應(yīng)用 —— Top K 問題

5.1 題目描述

5.2 解法步驟

5.3 復(fù)雜度分析

6. 最大索引堆

參考資料

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

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

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