博文位址

我的GitHub	我的部落格	我的微信	我的郵箱
baiqiantao		bqt20094	[email protected]

28 | 堆和堆排序：為什麼說堆排序沒有快速排序快？
- 堆的概念
- 如何存儲一個堆
- 堆上的主要操作
  - 堆化
  - 插入一個元素：從下往上的堆化
  - 删除堆頂元素：從上往下的堆化
    - 錯誤的方法
    - 正确的方法
- 堆排序算法
  - 建大頂堆
    - 建堆圖解
    - 建堆代碼
    - 建堆的時間複雜度
  - 排序過程：循環堆化
- 堆排序圖解及代碼
- 堆排序性能分析
- 為什麼快速排序比堆排序性能好
29 | 堆的應用：如何快速擷取到Top 10最熱門的搜尋關鍵詞？
- 堆的應用一：優先級隊列
  - 合并有序小檔案
    - 方案一：利用數組
    - 方案二：利用堆
  - 高性能定時器
- 堆的應用二：利用堆求 Top K
  - 靜态資料集
  - 動态資料集合
- 堆的應用三：利用堆求中位數
  - 求動态資料集合中的中位數
  - 求百分位的資料
- 解答開篇

堆是一種特殊的樹

，隻要滿足下面這兩點，它就是一個堆。

堆是一個 完全二叉樹
- 完全二叉樹要求，除了最後一層，其他層的節點個數都是滿的，最後一層的節點都靠左排列
堆中每一個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值
- 等價于，堆中每個節點的值都大于等于（或者小于等于）其左右子節點的值
- 每個節點的值都大于等于子樹中每個節點值的堆，叫做“大頂堆”
- 每個節點的值都小于等于子樹中每個節點值的堆，叫做“小頂堆”

完全二叉樹比較适合用

數組

來存儲，因為我們不需要存儲左右子節點的指針，單純地通過數組的

下标

，就可以找到一個節點的左右子節點和父節點。

數組中下标為 i 的節點的:

左子節點就是下标為 i∗2 的節點
右子節點就是下标為 i∗2 + 1
父節點就是下标為 i/2

往堆中插入一個元素
擷取、删除堆頂元素

往堆中插入一個元素或删除堆頂元素後，為了繼續滿足堆的兩個特性，我們需要對堆進行調整，這個過程就叫做

堆化

（heapify）。

堆化實際上有兩種，

從下往上

和

從上往下

。

堆化非常簡單，就是順着節點所在的路徑，向上或者向下，對比，然後交換。

一個包含 n 個節點的完全二叉樹，樹的高度不會超過 logn。堆化的過程是順着節點所在路徑比較交換的，是以堆化的時間複雜度跟樹的高度成正比，也就是

O(logn)

。插入資料和删除堆頂元素的主要邏輯就是堆化，是以，往堆中插入一個元素和删除堆頂元素的時間複雜度都是

O(logn)

我們讓新插入的節點與父節點

對比

大小，如果不滿足子節點小于等于父節點的大小關系，我們就

互換

兩個節點。一直重複這個過程，直到父子節點之間滿足剛說的那種大小關系。

public class Heap {
	private int[] a; // 數組，從下标1開始存儲資料
	private int n;  // 堆可以存儲的最大資料個數
	private int count; // 堆中已經存儲的資料個數
	
	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); // 交換元素
			i = i / 2;
		}
	}
}

堆頂元素存儲的就是堆中資料的最大值或者最小值。

假設我們構造的是大頂堆，堆頂元素就是最大的元素。當我們删除堆頂元素之後，就

需要把第二大的元素放到堆頂

，那第二大元素肯定會出現在

左或右子節點

中。然後我們再

疊代

地删除第二大節點，以此類推，直到葉子節點被删除。

不過這種方法有點問題，就是最後堆化出來的堆并不滿足

完全二叉樹

的特性。

實際上，我們稍微改變一下思路，就可以解決這個問題。

我們

把最後一個節點放到堆頂

，然後利用同樣的父子節點對比方法。對于不滿足父子節點大小關系的，互換兩個節點，并且重複進行這個過程，直到父子節點之間滿足大小關系為止。這就是從上往下的堆化方法。

因為我們移除的是數組中的最後一個元素，而在堆化的過程中，都是

交換

操作，不會出現數組中的“空洞”，是以這種方法堆化之後的結果，肯定滿足完全二叉樹的特性。

public void removeMax() {
	if (count == 0) return -1; // 堆中沒有資料
	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;
	}
}

借助于堆這種資料結構實作的排序算法，就叫做

堆排序

這種排序方法的時間複雜度非常穩定，是

O(nlogn)

，并且它還是

原地排序算法

我們首先将數組

原地

建成一個

大頂堆

。所謂

原地

就是，不借助另一個數組，就在原數組上操作。

建堆的過程，有兩種思路。

第一種是借助我們前面講的，在堆中插入一個元素的思路。盡管數組中包含 n 個資料，但是我們可以假設，起初堆中隻包含一個資料，就是下标為 1 的資料。然後，我們調用前面講的插入操作，将下标從 2 到 n 的資料依次插入到堆中。這樣我們就将包含 n 個資料的數組，組織成了堆。

第二種實作思路，跟第一種截然相反

第一種建堆思路的處理過程是， 從前往後 處理數組資料，并且每個資料插入堆中時，都是 從下往上堆化
而第二種實作思路是， 從後往前 處理數組，并且每個資料都是 從上往下堆化

因為葉子節點往下堆化隻能自己跟自己比較，是以我們直接從

最後一個非葉子節點

開始，依次堆化就行了。

下标為 n/2 + 1 到 n 的節點是 葉子節點 1 n/2 非葉子節點 n/2 最後一個非葉子節點

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; //對【交換後的結點】繼續進行上述操作
	}
}

堆排序的建堆過程的時間複雜度是

O(n)

因為葉子節點不需要堆化，是以需要堆化的節點從倒數第二層開始。每個節點堆化的過程中，需要比較和交換的節點個數跟這個節點的高度 k 成正比。

每一層的節點個數和對應的高度如下圖所示

将每一層的節點個數，乘以相應的高度，求和，就是算法時間複雜度：

把公式左右都乘以 2，就得到另一個公式 S2。我們将 S2 錯位對齊，并且用 S2 減去 S1，可以得到 S：

S 的中間部分是一個等比數列，是以最後可以用等比數列的求和公式來計算：

因為

h = logn

，代入公式 S，就能得到

S = O(n)

，是以，建堆的時間複雜度就是

O(n)

建堆結束之後，數組中的資料已經是按照

大頂堆

的特性來組織的，數組中的第一個元素就是堆頂，也就是最大的元素。

我們把 堆頂元素 跟 最後一個元素 交換，那最大元素就放到了下标為 n 的位置
交換以後，我們将剩下的 n−1 個元素通過 堆化 的方法重新建構成 大頂堆
重新堆化完成之後，我們再将 堆頂元素 跟下标是 n−1 的元素交換
重複這個過程，直到最後堆中隻剩一個元素，排序工作就完成了

// n 表示資料的個數，數組 a 中的資料從下标 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); //将剩下的待排序元素通過堆化的方法，重新建構成大頂堆
	}
}

空間複雜度：整個堆排序的過程，都隻需要極個别臨時存儲空間，是以堆排序是 原地排序算法
時間複雜度：堆排序包括建堆和排序兩個操作
- 建堆過程的時間複雜度是 O(n)
- 排序過程的時間複雜度是 O(nlogn)
- 堆排序整體的時間複雜度是 O(nlogn)
穩定性：堆排序 不是穩定的排序算法 ，因為在排序的過程，存在 将堆的最後一個節點跟堆頂節點互換 的操作，是以就有可能改變值相同資料的原始相對順序。

堆排序是一種原地的、時間複雜度為

O(nlogn)

的排序算法。快速排序平均情況下的時間複雜度也為

O(nlogn)

，甚至堆排序比快速排序的時間複雜度還要

穩定

。但是，在實際的軟體開發中，快速排序的性能要比堆排序好，這是為什麼呢？

主要有兩方面的原因。

第一點，堆排序 資料的通路方式 沒有快速排序友好

對于快速排序來說，資料是

順序通路

的。而對于堆排序來說，資料是

跳着通路

的。

堆排序中，最重要的一個操作就是資料的

堆化

，對堆頂節點進行堆化，會依次通路數組下标是 1，2，4，8 的元素，而不是像快速排序那樣，局部順序通路，這樣對

CPU 緩存

是不友好的。

第二點，對于同樣的資料，在排序過程中，堆排序算法的資料 交換次數 要多于快速排序

對于基于比較的排序算法來說，整個排序過程就是由兩個基本的操作組成的，比較和交換（或移動）。快速排序資料交換的次數不會比

逆序度

多。

但是堆排序的第一步是

建堆

，建堆的過程會打亂資料原有的相對先後順序，導緻原資料的有序度降低。比如，對于一組已經有序的資料來說，經過建堆之後，資料反而變得更無序了。

優先級隊列首先應該是一個

隊列

，隊列最大的特性就是

先進先出

。但是，在優先級隊列中，資料的出隊順序不是先進先出，而是按照優先級來，

優先級最高的，最先出隊

實作一個優先級隊列的方法有很多，但是用堆來實作是

最直接、最高效

的。這是因為，堆和優先級隊列非常相似。

一個堆就可以看作一個優先級隊列

。很多時候，它們隻是概念上的區分而已。

往優先級隊列中 插入 一個元素，就相當于往堆中插入一個元素
從優先級隊列中 取出 優先級最高的元素，就相當于取出 堆頂元素

優先級隊列的應用場景非常多，後面要講的很多資料結構和算法都要依賴它。比如， 赫夫曼編碼 、 圖的最短路徑 最小生成樹算法 等等。

很多語言中都提供了優先級隊列的實作，比如，Java 的

PriorityQueue

，C++ 的 priority_queue 等。

假設我們有 k 個小檔案，每個檔案的大小是 100MB，每個檔案中存儲的都是 有序 的字元串。我們希望将這 k 個小檔案合并成一個有序的大檔案。

我們從這 k 個檔案中，各取第一個字元串，放入

數組

中，然後比較大小，把最小的那個字元串放入合并後的大檔案中，并從數組中删除。

假設，這個最小的字元串來自于

m.txt

這個小檔案，我們就再從這個小檔案取下一個字元串，放到數組中，

重新比較大小

，并且選擇最小的放入合并後的大檔案，将它從數組中删除。依次類推，直到所有的檔案中的資料都放入到大檔案為止。

時間複雜度分析

假設每個小檔案中有 n 個字元串，則需要周遊 k * n 次
每次周遊需要插入一個新元素，并對有序的 k 個字元串重新排序
- 利用二分查找，查找插入位置時間複雜度為 logk
- 插入新元素并移動後面的元素位置時間複雜度為 k
整體時間複雜度為 k * n * (logk + k) ≈ k^2 * n

首先，每次從各個檔案中拿出第一個字元串，然後将這 k 個字元串組成一個小頂堆。此時堆頂元素，也就是優先級隊列隊首的元素，就是最小的字元串，我們将這個字元串放入到大檔案中，并将其從堆中删除。

m.txt

這個小檔案，我們就再從這個小檔案取下一個字元串，放入到堆中。循環這個過程，就可以将 k 個小檔案中的資料依次放入到大檔案中。

k * n
每次周遊需要往堆中插入一個新元素，并重新堆化，時間複雜度為常數 logk
k * n * logk klogk * n

比原來數組存儲的方式高效了一些，具體高效多少取決于 k 的大小。

假設我們有一個定時器，定時器中維護了很多

定時任務

，每個任務都設定了一個要觸發執行的時間點。定時器每過一個很小的機關時間（比如 1 秒），就掃描一遍任務，看是否有任務到達設定的執行時間。如果到達了，就拿出來執行。

針對這個問題，我們就可以用

優先級隊列

來解決。我們按照任務設定的執行時間，将這些任務存儲在優先級隊列中，隊列首部（也就是

小頂堆

的堆頂）存儲的是最先執行的任務。

這樣，定時器就不需要每隔 1 秒就掃描一遍任務清單了。它拿隊首任務的執行時間點，與目前時間點相減，得到一個時間間隔 T。

這個時間間隔 T 就是，從目前時間開始，需要等待多久，才會有第一個任務需要被執行。這樣，定時器就可以設定在 T 秒之後，再來執行任務。從目前時間點到（T-1）秒這段時間裡，定時器都不需要做任何事情。

當有新的任務插入時，先重新堆化，如果堆頂元素有變化，更新下定時器下次的查詢時間即可

當 T 秒時間過去之後，定時器取優先級隊列中隊首的任務執行。然後再計算新的隊首任務的執行時間點與目前時間點的內插補點，把這個值作為定時器執行下一個任務需要等待的時間。

這樣，定時器既不用間隔 1 秒就輪詢一次，也不用周遊整個任務清單，性能也就提高了。

也就是說資料集合事先确定，不會再變。

我們先從數組中取出前 k 個元素，利用這些元素維護一個大小為 K 的 小頂堆
然後順序周遊數組，從數組中取出資料與堆頂元素比較
- 如果比堆頂元素大，我們就把堆頂元素删除，并且将這個元素插入到堆中
- 如果比堆頂元素小，則不做處理，繼續周遊數組
這樣等數組中的資料都周遊完之後，堆中的資料就是前 K 大資料了

周遊數組需要

O(n)

的時間複雜度，一次堆化操作需要

O(logK)

的時間複雜度，整體時間複雜度就是

O(nlogK)

也就是說資料集合事先并不确定，有資料動态地加入到集合中。

實際上，我們可以一直都維護一個 K 大小的小頂堆，當有資料被添加到集合中時，我們就拿它與堆頂的元素對比。如果比堆頂元素大，我們就把堆頂元素删除，并且将這個元素插入到堆中；如果比堆頂元素小，則不做處理。這樣，無論任何時候需要查詢目前的前 K 大資料，我們都可以立刻傳回給他。

中位數就是處在中間位置的那個數。

假設資料是從 0 開始編号的

如果資料的個數是奇數，把資料從小到大排列，那第 n/2 + 1 個資料就是中位數
如果資料的個數是偶數，那處于中間位置的資料有兩個，第 n/2 個和第 n/2 + 1 個資料，這個時候，我們可以随意取一個作為中位數

對于一組靜态資料，中位數是固定的，我們可以先排序，第

n/2

個資料就是中位數。每次詢問中位數的時候，我們直接傳回這個固定的值就好了。是以，盡管排序的代價比較大，但是邊際成本會很小。但是，如果我們面對的是動态資料集合，中位數在不停地變動，如果再用先排序的方法，每次詢問中位數的時候，都要先進行排序，那效率就不高了。

借助堆這種資料結構，我們不用排序，就可以非常高效地實作求中位數操作。

我們需要維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中存儲前半部分資料，小頂堆中存儲後半部分資料，且

小頂堆中的資料都大于大頂堆中的資料

如果有 n 個資料，我們先從小到大排序，然後将前

n/2 + n%2

個資料存儲在大頂堆中，後

n/2

個資料存儲在小頂堆中。這樣，

大頂堆中的堆頂元素

就是我們要找的

中位數

當新添加一個資料的時候，我們如何調整兩個堆，讓大頂堆中的堆頂元素繼續是中位數呢？

如果新加入的資料小于等于大頂堆的堆頂元素，我們就将這個新資料插入到大頂堆；否則，我們就将這個新資料插入到小頂堆。
插入後，如果兩個堆中的資料個數不符合前面的約定，我們可以 将一個堆的堆頂元素移動到另一個堆中

于是，我們就可以利用一個大頂堆和一個小頂堆，實作在動态資料集合中求中位數的操作。

插入資料因為需要涉及堆化，是以時間複雜度為

O(logn)

，但是求中位數我們隻需要傳回大頂堆的堆頂元素就可以了，是以整體時間複雜度就是

O(logn)

利用兩個堆不僅可以快速求出中位數，還可以快速求其他百分位的資料，原理是類似的。

中位數的概念就是将資料從小到大排列，處于中間位置，就叫中位數，這個資料會大于等于前面

50%

的資料。99 百分位數的概念可以類比中位數，如果将一組資料從小到大排列，這個 99 百分位數就是大于前面

99%

資料的那個資料。

如果有 n 個資料，将資料從小到大排列之後，99 百分位數大約就是第

n * 99%

個資料。

假設目前總資料的個數是 n，我們維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中儲存

n*99%

個資料，小頂堆中儲存

n*1%

大頂堆堆頂的資料

99%

響應時間。

每次插入一個資料的時候，我們要判斷這個資料跟大頂堆和小頂堆堆頂資料的大小關系，然後決定插入到哪個堆中。如果這個新插入的資料比大頂堆的堆頂資料小，那就插入大頂堆，否則就插入小頂堆。

但是，為了保持大頂堆中的資料占

99%

，小頂堆中的資料占

1%

，在每次新插入資料之後，我們都要重新計算大頂堆和小頂堆中的資料個數是否還符合

99:1

這個比例。如果不符合，我們就

将一個堆的堆頂資料移動到另一個堆

，直到滿足這個比例。

假設現在我們有一個包含 10 億個搜尋關鍵詞的日志檔案，如何快速擷取到 Top 10 最熱門的搜尋關鍵詞呢？

因為使用者搜尋的關鍵詞，有很多可能都是重複的，是以我們首先要統計每個搜尋關鍵詞出現的頻率。我們可以通過 散清單 來記錄關鍵詞及其出現的次數。
分片：10 億條關鍵詞太多，消耗的記憶體太大，需要先通過雜湊演算法分片到 10 個檔案中
- 我們先周遊這 10 億個關鍵詞，并且通過某個雜湊演算法對其求哈希值
- 然後将哈希值同 10 取模，這樣就可以将 10 億條搜尋關鍵詞分片到 10 個檔案中
- 并且，相同的搜尋關鍵詞都會被分到同一個小檔案中
散清單：我們順序掃描每個包含 1 億條搜尋關鍵詞的檔案，當掃描到某個關鍵詞時，先去散清單中查詢
- 如果存在，我們就将對應的次數 +1
- 如果不存在，我們就将它插入到散清單，并記錄次數為 1
- 周遊完後，散清單中就存儲了不重複的搜尋關鍵詞以及出現的次數
小頂堆：我們針對每個散清單，建立一個大小為 10 的小頂堆
- 周遊散清單，依次取出每個搜尋關鍵詞及對應出現的次數，然後與堆頂的搜尋關鍵詞對比
- 如果出現次數比堆頂搜尋關鍵詞的次數多，那就删除堆頂的關鍵詞，将這個出現次數更多的關鍵詞加入到堆中
- 當周遊完整個散清單中的搜尋關鍵詞之後，堆中的搜尋關鍵詞就是目前散清單中出現次數最多的 Top 10 搜尋關鍵詞了
小頂堆：把這個 10 個 Top 10 放在一塊，然後取這 100 個關鍵詞中的 Top 10 個關鍵詞即可

2021-09-03

本文來自部落格園，作者：白乾濤，轉載請注明原文連結：https://www.cnblogs.com/baiqiantao/p/15224654.html

資料結構與算法之美-10 堆優先級隊列 [MD]

目錄

繼續閱讀

無論是傳統燃油車還是新能源汽車，安全問題一直是消費者選車時的重中之重，這關系到消費者的切身利益。對于岚圖汽車來說，安全始

#創作靈感2021年款星途LX追風維修手冊電路圖保險絲繼電器位置圖解說明#星途追風#星途LX

我是即将退休的國企職工，翻翻曆史工資賬，看看我的工資成長經曆。1985年:32元（鄉鎮企業）。1991年:86元（鄉鎮企

聯發科天玑高、中、低端如何分辨？一分鐘徹底搞清！天玑處理器天梯圖實用版。一分鐘徹底搞清天玑處理器，高中低端劃分以及根據你

最近的大熱電影#芭比#中，Ken的扮演者高司令同時佩戴了三枚泰格豪雅古董表，包括1971年産的18K金Ref.1158C

MATLAB環境下信号的同步壓縮變換脊線提取方法算法運作環境為MATLABR2021B及以上，執行号的同步壓縮變換脊線提

過去幾年，FurlanMarri應該是最成功的新興品牌。2021年創立，在同年的日内瓦進階鐘表大賞上斬獲獎項，二級市場部

一汽豐田皇冠陸放2021-2023年款維修手冊電路圖車身維修手冊FAWToyotaCrownLuFang2021-202

Gdal讀寫栅格資料

因為要找以往的郵件，于是就在郵箱裡面翻找。需要找的郵件多，要根據時間排序，于是按要求在郵箱裡面翻找着時間。2022年某月

202020212022冬天

【新到車型】雷克薩斯2020款ES200豪華版【上牌時間】2021年3月【行駛裡程】4.7萬KM【4S店指導價】30.9

【新到車型】2021款寶馬225i四門轎跑車M運動耀夜套裝【上牌時間】2021年3月【行駛裡程】2.4萬公裡【4S店指導

甲子路win11系統max2024和max2022corona10.1vray6.1ps（Bata）AIV25.0版本C

MATLAB環境下計算時間同步平均信号的差分信号算法運作環境為MATLABR2021B，計算時間同步平均信号的差分信号。

2021年複旦大學961真題回顧第一部分資料結構第二部分軟體工程第三部分計算機系統基礎

資料結構與算法之美-10 堆 優先級隊列 [MD]

目錄

繼續閱讀

資料結構與算法之美-10 堆優先級隊列 [MD]