前言：本篇文章只是記錄王爭的數(shù)據(jù)結(jié)構(gòu)與算法之美的學(xué)習(xí)筆記，寫下來能強迫自己系統(tǒng)的再過一遍梦染，加深理解。這門課以實際開發(fā)中遇到的問題為例朴皆，引入解決問題涉及到的的數(shù)據(jù)結(jié)構(gòu)和算法帕识，但不會講的太細(xì)，最好結(jié)合一本實體書進行學(xué)習(xí)遂铡。

1. 堆的概念

堆是一種特殊的樹肮疗，需要滿足下面兩點：

• 堆是一個完全二叉樹
• 堆中每一個節(jié)點的值都必須大于等于（或小于等于）其左右子樹中每個節(jié)點的值

大頂堆和小頂堆就是根據(jù)第二條區(qū)分的：

• 每個節(jié)點的值都大于等于子樹中每個節(jié)點值的堆為大頂堆
• 每個節(jié)點的值都小于等于子樹中每個節(jié)點值的堆為小頂堆

如下圖：

image.png

2. 堆的實現(xiàn)

2.1 堆的存儲

上面說堆是一個完全二叉樹，完全二叉樹比較適合用數(shù)組來存儲扒接。用數(shù)組存儲完全二叉樹節(jié)省內(nèi)存空間族吻，單純的通過數(shù)組下標(biāo)，就可以找到一個節(jié)點的左右子節(jié)點和父節(jié)點珠增，如下圖所示：

image.png

從上圖中可以看到：

• 數(shù)組中下標(biāo)為 i 的節(jié)點的左子節(jié)點的下標(biāo)為i * 2
• 右子節(jié)點就是下標(biāo)為i * 2 + 1的節(jié)點
• 父節(jié)點就是下標(biāo)為i / 2的節(jié)點

2.2 堆中插入一個元素

如果把新插入的元素放到堆的最后超歌，如果不符合堆的特性，就需要調(diào)整蒂教，調(diào)整的過程稱為堆化巍举。如下圖所示：

image.png

堆化就是順著節(jié)點所在的路徑，向上或者向下凝垛，對比懊悯，然后交換，所以堆化分為兩種：

• 從下往上
• 從上往下

以從下往上為例梦皮，堆化的過程就是讓新插入的節(jié)點和父節(jié)點對比大小炭分，如果不滿足子節(jié)點小于等于父節(jié)點的關(guān)系，就互換兩個結(jié)點剑肯，一直重復(fù)這個過程捧毛，直到滿足，如下圖所示：

image.png

代碼實現(xiàn)如下：

public class Heap {
  private int[] a; // 數(shù)組，從下標(biāo)1開始存儲數(shù)據(jù)
  private int n;  // 堆可以存儲的最大數(shù)據(jù)個數(shù)
  private int count; // 堆中已經(jīng)存儲的數(shù)據(jù)個數(shù)

  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }

  public void insert(int data) {
    if (count >= n) return; // 堆滿了
    ++count;
    a[count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
      swap(a, i, i/2); // swap()函數(shù)作用：交換下標(biāo)為i和i/2的兩個元素
      i = I/2;
    }
  }
 }

2.3 刪除堆頂元素

堆頂元素就是堆中數(shù)據(jù)的最大值或者最小值呀忧。

刪除操作過程：把最后一個節(jié)點放到堆頂师痕，然后利用同樣的父子節(jié)點對比方法，對于不滿足父子節(jié)點大小關(guān)系的而账，互換兩個節(jié)點胰坟，并且重復(fù)此過程，直到父子節(jié)點之間滿足大小關(guān)系為止泞辐。

這就是從上往下的堆化方法笔横，如下圖所示：

image.png

代碼如下：

public void removeMax() {
  if (count == 0) return -1; // 堆中沒有數(shù)據(jù)
  a[1] = a[count];
  --count;
  heapify(a, count, 1);
}

private void heapify(int[] a, int n, int i) { // 自上往下堆化
  while (true) {
    int maxPos = I;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = I*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

一個包含 n 個節(jié)點的完全二叉樹，樹的高度不會超過log2n咐吼，堆化的過程是順著節(jié)點所在路徑比較交換的狠裹，所以堆化的時間復(fù)雜度是 O(logn)。插入一個元素和刪除堆頂元素的主要邏輯就是堆化汽烦，時間復(fù)雜度都是O(logn)。

3. 基于堆實現(xiàn)排序

基于堆這種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的排序算法叫做堆排序莉御，時間復(fù)雜度非常穩(wěn)定撇吞，是 O(nlogn)，并且還是原地排序算法礁叔。

堆排序的過程大致分為 兩個步驟：建堆 和 排序牍颈。

3.1 建堆

首先需要將數(shù)組原地建成一個堆，有兩種思路：

• 第一種跟堆中插入一個元素一樣琅关，起初堆中只包含一個數(shù)據(jù)煮岁，下標(biāo)為 1，然后用前面的插入操作涣易，將2 到 n 的數(shù)據(jù)依次插入到堆中画机，從前往后處理數(shù)組數(shù)據(jù)，并且每個數(shù)據(jù)插入堆中時新症，都是從下往上堆化
• 第二種跟第一種截然相反步氏，是從后往前處理數(shù)組，并且每個數(shù)據(jù)都是從上往下堆化

第二種實現(xiàn)思路的分解圖：

image.png

image.png

實現(xiàn)代碼：

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = I;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = I*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

代碼中只對下標(biāo)從1到 n/2的數(shù)據(jù)進行了堆化徒爹，因為對于完全二叉樹來說荚醒，下標(biāo)從n/2 + 1 到 n 的節(jié)點都是葉子結(jié)點。

完全二叉樹中最后一個節(jié)點的下標(biāo)為 n隆嗅，那么其父節(jié)點就是最后一個非葉子結(jié)點界阁，下標(biāo)為 n/2 ，之后的節(jié)點都是葉子結(jié)點了胖喳，也就是n/2 + 1 到 n 的節(jié)點都是葉子節(jié)點泡躯。

建堆的時間復(fù)雜度：
堆排序的建堆過程的時間復(fù)雜度是 O(n)。

推導(dǎo)過程：
葉子節(jié)點不需要堆化，所以需要堆化的節(jié)點從倒數(shù)第二層開始精续，每個節(jié)點堆化的過程中坝锰，需要比較和交換的節(jié)點個數(shù)，跟這個節(jié)點的高度 k 成正比重付。

下圖把每一層的節(jié)點個數(shù)和對應(yīng)的高度畫了出來顷级，我們只需要將每個節(jié)點的高度求和，得出的就是建堆的時間復(fù)雜度：

image.png

將每個非葉子節(jié)點的高度求和确垫，就是下面的公式：

image.png

image.png

最終的結(jié)果就是：

image.png

因為 h = log2n弓颈，帶入公式，得到 S = O(n)删掀，所以建堆的時間復(fù)雜度就是 O(n)翔冀。

3.2 排序

排序主要使用了類似“刪除堆頂元素”的操作，因為數(shù)組中第一個元素就是堆頂披泪，也是最大的元素纤子，把堆頂元素放到下標(biāo)為 n 的位置，然后再通過堆化方法款票，將剩下 n - 1個元素重新構(gòu)建成堆控硼。堆化完成之后，我們再取堆頂?shù)脑匕伲诺较聵?biāo)是 n?1 的位置卡乾，一直重復(fù)這個過程，直到最后堆中只剩下標(biāo)為 1 的一個元素缚够，排序工作就完成了幔妨。如下圖：

image.png

代碼如下：

// n表示數(shù)據(jù)的個數(shù)，數(shù)組a中的數(shù)據(jù)從下標(biāo)1到n的位置谍椅。
public static void sort(int[] a, int n) {
  buildHeap(a, n);
  int k = n;
  while (k > 1) {
    swap(a, 1, k);
    --k;
    heapify(a, k, 1);
  }
}

3.3 堆排序分析

堆排序是原地排序算法误堡，只需要極個別臨時存儲空間。
堆排序包括建堆和排序兩個操作雏吭，建堆的時間復(fù)雜度是 O(n)埂伦，排序的時間復(fù)雜度是O(nlogn)，所以思恐，堆排序整體的時間復(fù)雜度是 O(nlogn)沾谜。

堆排序不是穩(wěn)定的排序算法，因為在排序的過程胀莹，存在將堆的最后一個節(jié)點跟堆頂節(jié)點互換的操作基跑，所以就有可能改變值相同數(shù)據(jù)的原始相對順序。

為什么快排要比堆排序性能好描焰？

• 堆排序數(shù)據(jù)訪問的方式?jīng)]有快排友好
  快排是順序訪問的媳否，堆排序數(shù)據(jù)是跳著訪問的栅螟，對 CPU 緩存不友好
• 對于同樣的數(shù)據(jù)，在排序過程中篱竭，堆排序算法的數(shù)據(jù)交換次數(shù)要多于快速排序

4. 堆的應(yīng)用

4.1 優(yōu)先級隊列

一個堆就可以看作一個優(yōu)先級隊列力图，往優(yōu)先級隊列中插入一個元素，就相當(dāng)于往堆中插入一個元素掺逼，從優(yōu)先級隊列中取出優(yōu)先級最高的元素吃媒，就相當(dāng)于取出堆頂元素。

4.1.1 合并有序小文件

場景：有 100 個小文件吕喘，大小都是 100MB赘那，存儲的都是有序的字符串，想將這些 100 個小文件合并成一個有序的大文件氯质。

就需要用到優(yōu)先級隊列募舟，也可以說是堆。先從 100 個文件中闻察，各取第一個字符串拱礁，然后構(gòu)建一個小頂堆，堆頂?shù)脑匾簿褪莾?yōu)先級隊列隊首的元素辕漂，就是最小的字符串呢灶。將這個字符串放入到大文件中，然后將其從堆中刪除钮热。然后再從那個小文件中取出下一個字符串，放入到堆中烛芬，循環(huán)這個過程就可以了隧期。

4.1.2 高性能定時器

場景：有一個定時器，維護了很多定時任務(wù)赘娄，每個任務(wù)都設(shè)定了一個要觸發(fā)執(zhí)行的時間點仆潮。定時器每過一個很小的單位時間（比如 1 秒），就掃描一遍任務(wù)遣臼，看是否有任務(wù)到達設(shè)定的執(zhí)行時間性置。如果到達了，就拿出來執(zhí)行揍堰。

image.png

這樣每隔 1 秒就掃描一遍任務(wù)列表比較低效鹏浅。我們可以使用優(yōu)先級隊列來解決：

• 按照任務(wù)設(shè)定的時間，將這些任務(wù)存儲在優(yōu)先級隊列中屏歹，隊列首部（小頂堆的堆頂）存儲的是最先執(zhí)行的任務(wù)
• 定時器就每次拿到隊首任務(wù)的執(zhí)行時間點隐砸，和當(dāng)前時間點相減，得到一個時間間隔 T蝙眶，定時器設(shè)定在 T 秒之后季希，執(zhí)行任務(wù)
• 隊首任務(wù)執(zhí)行完成之后，再計算新的隊首任務(wù)的執(zhí)行時間點和當(dāng)前時間點的差值，把這個值作為定時器執(zhí)行下一個任務(wù)需要等待的時間
• 直到任務(wù)都完成

4.2 利用堆求 Top K

求 Top K 的問題可以抽象成兩類：

• 針對靜態(tài)數(shù)據(jù)集合(數(shù)據(jù)集合事先已經(jīng)確定式塌，不會再變)
• 針對動態(tài)數(shù)據(jù)集合(數(shù)據(jù)集合可能會再添加新的數(shù)據(jù))

針對于一個 n 個數(shù)據(jù)的數(shù)組博敬，要查找前 K 大數(shù)據(jù)：

• 1.維護一個大小為 K 的小頂堆
• 2.順序遍歷數(shù)組，和堆頂元素比較
• 3.如果比堆頂元素大峰尝，就把堆頂元素刪除偏窝，將這個元素插入到堆中
• 4.如果比堆頂元素小，就繼續(xù)遍歷
• 5.遍歷完成之后境析，小頂堆中的數(shù)據(jù)就是前 K 大數(shù)據(jù)了

遍歷數(shù)組的時間復(fù)雜度為 O(n)囚枪，堆化的時間復(fù)雜度為 O(logK)主守，所以最壞的時間復(fù)雜度就是O(nlogK)蛤奢。

針對于動態(tài)數(shù)據(jù)求 Top K 就是實時獲取 TopK肖抱，其中有兩個操作叛拷，一個是添加數(shù)據(jù)旱函，另一個獲取當(dāng)前的前 K 大數(shù)據(jù)批钠。
可以一直維護一個 K 大小的小頂堆前计，當(dāng)有數(shù)據(jù)被添加到集合中時潜秋，和堆頂?shù)脑剡M行對比曲掰，進行堆化疾捍。

4.3 求中位數(shù)

就是求動態(tài)數(shù)據(jù)集合中的中位數(shù)，如下圖：

image.png

針對于靜態(tài)數(shù)據(jù)：

• 中位數(shù)是固定的栏妖，先進行排序
• 獲取第n/2 個數(shù)據(jù)就是中位數(shù)

針對于動態(tài)數(shù)據(jù)：

• 維護兩個堆：一個大頂堆 & 一個小頂堆
• 大頂堆存儲前半部分?jǐn)?shù)據(jù)乱豆，小頂堆存儲后半部分?jǐn)?shù)據(jù)，并且小頂堆中的數(shù)據(jù)都大于大頂堆中的數(shù)據(jù)

如果有 n 個數(shù)據(jù)：

• n 是偶數(shù)吊趾，從小到大排序宛裕，前 n/2 個數(shù)據(jù)存儲在大頂堆中，后n/2個數(shù)據(jù)存儲在小頂堆中论泛，大頂堆中的堆頂元素就是中位數(shù)
• n 是奇數(shù)揩尸，大頂堆存儲 n/2 + 1 個元素，小頂堆存儲 n/2個數(shù)據(jù)

image.png

當(dāng)有數(shù)據(jù)要加入的時候屁奏，需要調(diào)整兩個堆：

• 如果新加入的數(shù)據(jù)小于等于大頂堆的堆頂元素岩榆，就插入到大頂堆
• 否則，插入到小頂堆
• 如果出現(xiàn)兩個堆中數(shù)據(jù)個數(shù)不符合前面的情況坟瓢，需要從一個堆中取堆頂元素移動到另一個堆勇边，調(diào)整堆中數(shù)據(jù)

image.png

時間復(fù)雜度分析：

• 插入數(shù)據(jù)涉及到堆化，時間復(fù)雜度為 O(logn)
• 求中位數(shù)直接取大頂堆的堆頂元素折联，為 O(1)

5. 思考題

假設(shè)現(xiàn)在我們有一個包含 10 億個搜索關(guān)鍵詞的日志文件粥诫，如何能快速獲取到熱門榜 Top 10 的搜索關(guān)鍵詞？場景限定為單機崭庸，可以使用的內(nèi)存為 1GB怀浆。

• 1.將 10 億條搜索關(guān)鍵詞通過哈希算法分片到 10 個文件中
  構(gòu)建 10 個空文件谊囚，從 0-9 編號，對10 億個關(guān)鍵詞通過哈希算法求哈希值执赡，然后同 10 取模镰踏，存儲到對應(yīng)編號的文件中
• 2.利用散列表存儲關(guān)鍵詞及其出現(xiàn)的次數(shù)（遍歷文件中的關(guān)鍵詞，存入散列表中）沙合，每個文件對應(yīng)維護一個小頂堆獲取 top10奠伪，10 個文件，一共 10 個 top10
• 3.將這個 10 個 top10 放一塊首懈，取這 100 個關(guān)鍵詞中绊率，次數(shù)最多的 10 個關(guān)鍵字即可

6. 練習(xí)

• 堆的插入和刪除
• 堆排序的實現(xiàn)
• 求 topk
• 求中位數(shù)
• 高效定時器
• 大文件的關(guān)鍵字統(tǒng)計