加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
我們今天講另外一種特殊的樹，“堆”（Heap）。堆這種數據結構的應用場景非常多，最經典的莫過於堆排序了。堆排序是一種原地的、時間複雜度為 O(nlogn) 的排序算法。
前面我們學過快速排序，平均情況下，它的時間複雜度為 O(nlogn)。儘管這兩種排序算法的時間複雜度都是 O(nlogn)，甚至堆排序比快速排序的時間複雜度還要穩定，但是，在實際的軟件開發中，快速排序的性能要比堆排序好，這是為什麼呢？
現在，你可能還無法回答，甚至對問題本身還有點疑惑。沒關係，帶著這個問題，我們來學習今天的內容。等你學完之後，或許就能回答出來了。
如何理解“堆”？
前面我們提到，堆是一種特殊的樹。我們現在就來看看，什麼樣的樹才是堆。我羅列了兩點要求，只要滿足這兩點，它就是一個堆。
- 堆是一個完全二叉樹；
- 堆中每一個節點的值都必須大於等於（或小於等於）其子樹中每個節點的值。
我分別解釋一下這兩點。
第一點，堆必須是一個完全二叉樹。還記得我們之前講的完全二叉樹的定義嗎？完全二叉樹要求，除了最後一層，其他層的節點個數都是滿的，最後一層的節點都靠左排列。
第二點，堆中的每個節點的值必須大於等於（或者小於等於）其子樹中每個節點的值。實際上，我們還可以換一種說法，堆中每個節點的值都大於等於（或者小於等於）其左右子節點的值。這兩種表述是等價的。
對於每個節點的值都大於等於子樹中每個節點值的堆，我們叫作“大頂堆”。對於每個節點的值都小於等於子樹中每個節點值的堆，我們叫作“小頂堆”。
定義解釋清楚了，你來看看，下面這幾個二叉樹是不是堆？
其中第 1個和第 2 個是大頂堆，第 3 個是小頂堆，第 4 個不是堆。除此之外，從圖中還可以看出來，對於同一組數據，我們可以構建多種不同形態的堆。
如何實現一個堆？
要實現一個堆，我們先要知道，堆都支持哪些操作以及如何存儲一個堆。
我之前講過，完全二叉樹比較適合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的。因為我們不需要存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。
我畫了一個用數組存儲堆的例子，你可以先看下。
從圖中我們可以看到，數組中下標為 ii 的節點的左子節點，就是下標為 i∗2 的節點，右子節點就是下標為 i∗2+1 的節點，父節點就是下標為 i2 的節點。
知道了如何存儲一個堆，那我們再來看看，堆上的操作有哪些呢？我羅列了幾個非常核心的操作，分別是往堆中插入一個元素和刪除堆頂元素。（如果沒有特殊說明，我下面都是拿大頂堆來講解）。
1. 往堆中插入一個元素
往堆中插入一個元素後，我們需要繼續滿足堆的兩個特性。
如果我們把新插入的元素放到堆的最後，你可以看我畫的這個圖，是不是不符合堆的特性了？於是，我們就需要進行調整，讓其重新滿足堆的特性，這個過程我們起了一個名字，就叫作堆化（heapify）。
堆化實際上有兩種，從下往上和從上往下。這裡我先講從下往上的堆化方法。
堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然後交換。
我這裡畫了一張堆化的過程分解圖。我們可以讓新插入的節點與父節點對比大小。如果不滿足子節點小於等於父節點的大小關係，我們就互換兩個節點。一直重複這個過程，直到父子節點之間滿足剛說的那種大小關係。
我將上面講的往堆中插入數據的過程，翻譯成了代碼，你可以結合著一塊看。
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); // swap() 函數作用：交換下標為 i 和 i/2 的兩個元素
i = i/2;
}
}
}
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;
}
}
我們知道，一個包含 n 個節點的完全二叉樹，樹的高度不會超過 log2n。堆化的過程是順著節點所在路徑比較交換的，所以堆化的時間複雜度跟樹的高度成正比，也就是 O(logn)。插入數據和刪除堆頂元素的主要邏輯就是堆化，所以，往堆中插入一個元素和刪除堆頂元素的時間複雜度都是 O(logn)。
如何基於堆實現排序？
前面我們講過好幾種排序算法，我們再來回憶一下，有時間複雜度是 O(n2) 的冒泡排序、插入排序、選擇排序，有時間複雜度是 O(nlogn) 的歸併排序、快速排序，還有線性排序。
這裡我們藉助於堆這種數據結構實現的排序算法，就叫作堆排序。這種排序方法的時間複雜度非常穩定，是 O(nlogn)，並且它還是原地排序算法。如此優秀，它是怎麼做到的呢？
我們可以把堆排序的過程大致分解成兩個大的步驟，建堆和排序。
1. 建堆
我們首先將數組原地建成一個堆。所謂“原地”就是，不借助另一個數組，就在原數組上操作。建堆的過程，有兩種思路。
第一種是藉助我們前面講的，在堆中插入一個元素的思路。儘管數組中包含 n 個數據，但是我們可以假設，起初堆中只包含一個數據，就是下標為 1 的數據。然後，我們調用前面講的插入操作，將下標從 2 到 n 的數據依次插入到堆中。這樣我們就將包含 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;
}
}
你可能已經發現了，在這段代碼中，我們對下標從 n2 開始到 1 的數據進行堆化，下標是 n2+1 到 n 的節點是葉子節點，我們不需要堆化。實際上，對於完全二叉樹來說，下標從 n2+1 到 n 的節點都是葉子節點。
現在，我們來看，建堆操作的時間複雜度是多少呢？
每個節點堆化的時間複雜度是 O(logn)，那 n2+1 個節點堆化的總時間複雜度是不是就是 O(nlogn) 呢？這個答案雖然也沒錯，但是這個值還是不夠精確。實際上，堆排序的建堆過程的時間複雜度是 O(n)。我帶你推導一下。
因為葉子節點不需要堆化，所以需要堆化的節點從倒數第二層開始。每個節點堆化的過程中，需要比較和交換的節點個數，跟這個節點的高度 k 成正比。
我把每一層的節點個數和對應的高度畫了出來，你可以看看。我們只需要將每個節點的高度求和，得出的就是建堆的時間複雜度。
我們將每個非葉子節點的高度求和，就是下面這個公式：
這個公式的求解稍微有點技巧，不過我們高中應該都學過：把公式左右都乘以 2，就得到另一個公式 S2。我們將 S2 錯位對齊，並且用 S2 減去 S1，可以得到 S。
S 的中間部分是一個等比數列，所以最後可以用等比數列的求和公式來計算，最終的結果就是下面圖中畫的這個樣子。
因為 h=log2n，代入公式 S，就能得到 S=O(n)，所以，建堆的時間複雜度就是 O(n)。
2. 排序
建堆結束之後，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。我們把它跟最後一個元素交換，那最大元素就放到了下標為 n 的位置。
這個過程有點類似上面講的“刪除堆頂元素”的操作，當堆頂元素移除之後，我們把下標為 n 的元素放到堆頂，然後再通過堆化的方法，將剩下的 n−1 個元素重新構建成堆。堆化完成之後，我們再取堆頂的元素，放到下標是 n−1 的位置，一直重複這個過程，直到最後堆中只剩下標為 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)。
堆排序不是穩定的排序算法，因為在排序的過程，存在將堆的最後一個節點跟堆頂節點互換的操作，所以就有可能改變值相同數據的原始相對順序。
今天的內容到此就講完了。我這裡要稍微解釋一下，在前面的講解以及代碼中，我都假設，堆中的數據是從數組下標為 1 的位置開始存儲。那如果從 0 開始存儲，實際上處理思路是沒有任何變化的，唯一變化的，可能就是，代碼實現的時候，計算子節點和父節點的下標的公式改變了。
如果節點的下標是 i，那左子節點的下標就是 2∗i+1，右子節點的下標就是 2∗i+2，父節點的下標就是 i−12。
解答開篇
現在我們來看開篇的問題，在實際開發中，為什麼快速排序要比堆排序性能好？
我覺得主要有兩方面的原因。
第一點，堆排序數據訪問的方式沒有快速排序友好。
對於快速排序來說，數據是順序訪問的。而對於堆排序來說，數據是跳著訪問的。 比如，堆排序中，最重要的一個操作就是數據的堆化。比如下面這個例子，對堆頂節點進行堆化，會依次訪問數組下標是 1，2，4，8的元素，而不是像快速排序那樣，局部順序訪問，所以，這樣對 CPU 緩存是不友好的。
第二點，對於同樣的數據，在排序過程中，堆排序算法的數據交換次數要多於快速排序。
我們在講排序的時候，提過兩個概念，有序度和逆序度。對於基於比較的排序算法來說，整個排序過程就是由兩個基本的操作組成的，比較和交換（或移動）。快速排序數據交換的次數不會比逆序度多。
但是堆排序的第一步是建堆，建堆的過程會打亂數據原有的相對先後順序，導致原數據的有序度降低。比如，對於一組已經有序的數據來說，經過建堆之後，數據反而變得更無序了。
對於第二點，你可以自己做個試驗看下。我們用一個記錄交換次數的變量，在代碼中，每次交換的時候，我們就對這個變量加一，排序完成之後，這個變量的值就是總的數據交換次數。這樣你就能很直觀地理解我剛剛說的，堆排序比快速排序交換次數多。
內容小結
今天我們講了堆這種數據結構。堆是一種完全二叉樹。它最大的特性是：每個節點的值都大於等於（或小於等於）其子樹節點的值。因此，堆被分成了兩類，大頂堆和小頂堆。
堆中比較重要的兩個操作是插入一個數據和刪除堆頂元素。這兩個操作都要用到堆化。插入一個數據的時候，我們把新插入的數據放到數組的最後，然後從下往上堆化；刪除堆頂數據的時候，我們把數組中的最後一個元素放到堆頂，然後從上往下堆化。這兩個操作時間複雜度都是 O(logn)。
除此之外，我們還講了堆的一個經典應用，堆排序。堆排序包含兩個過程，建堆和排序。我們將下標從 n2 到 1 的節點，依次進行從上到下的堆化操作，然後就可以將數組中的數據組織成堆這種數據結構。接下來，我們迭代地將堆頂的元素放到堆的末尾，並將堆的大小減一，然後再堆化，重複這個過程，直到堆中只剩下一個元素，整個數組中的數據就都有序排列了。
閱讀更多 xiuxiuing 的文章
