目錄
最直觀的思路
更優化的思路（自底向上的構建）
第一步：重新審視問題
第二步：找到規律，形成策略
用一個實例來推演
第三步：編寫代碼
總結與分析
我們來深入探討“創建堆”（或者叫“堆化”，Heapify）的過程。這是堆結構中一個非常核心且巧妙的操作。
我們的任務：給定一個包含任意數據的普通數組，如何最高效地將它原地轉換成一個合法的堆？
例如，給定數組 arr = [3, 5, 80, 100, 70, 60]，我們需要將它重新排列，使其滿足大頂堆的屬性。
同樣，我們從第一性原理出發，探索解決之道。
最直觀的思路
我們已經掌握了向堆中 insert 一個新元素的方法。一個非常自然的想法是：
-
假設我們有一個空的堆。
-
然后我們遍歷給定的數組，把數組中的每一個元素，依次
insert到這個新堆中。 -
當所有元素都插入完畢后，我們不就得到了一個合法的堆嗎？
?這個思路是完全正確的，它利用了我們已有的“工具”（insert 函數）。
數據結構：在堆中插入元素（Inserting In a Heap）-CSDN博客
我們知道，每次 insert 操作的核心是“上浮”(Sift Up)，其時間復雜度是 O(logk)，其中 k 是堆中當時的元素數量。
推演過程：
-
插入第1個元素：代價是 O(log1)
-
插入第2個元素：代價是 O(log2)
-
...
-
插入第 N 個元素：代價是 O(logN)
把所有這些代價加起來，總的時間復雜度近似為 O(NlogN)。
📍小結一下方法一：
-
優點：思路簡單，容易理解，直接復用了
insert操作。 -
缺點：效率不是最優的。O(NlogN) 雖然不錯，但我們不禁要問：有沒有可能更快？
這個問題，促使我們去尋找一個更根本、更高效的方法。
更優化的思路（自底向上的構建）
第一步：重新審視問題
我們手里的數組，本身就可以被看作一棵“完全二叉樹”，只不過它的節點值不滿足“堆序屬性”。 我們的目標就是修復這個屬性。
讓我們從一個新的角度來觀察這棵樹，思考一個問題：
在這棵“亂序”的樹中，哪些部分已經天然滿足堆的屬性了？
答案是：所有的葉子節點 (leaf nodes)。
一個葉子節點，因為它沒有孩子，所以它自己就構成了一個合法的、大小為1的堆。 “父節點 >= 子節點” 這個條件因為沒有子節點而天然成立。
這是一個至關重要的突破口！
第二步：找到規律，形成策略
在一個用數組表示的、大小為 n 的完全二叉樹中，哪些是葉子節點呢？
-
對于下標為
i的節點，它的左孩子是2*i + 1。如果2*i + 1 >= n，那么它就沒有左孩子，也就必然沒有右孩子，它就是葉子節點。 -
我們可以推斷出，從下標
n/2到n-1的所有節點，都是葉子節點。
既然所有的葉子節點都已經是“合法”的堆了，我們就不需要對它們做任何操作。我們需要修復的，僅僅是那些非葉子節點。
最后一個非葉子節點在哪里？它就在第一個葉子節點的前面，也就是下標為 (n/2) - 1 的位置。
這啟發了我們一個自底向上的修復策略：
1??我們從最后一個非葉子節點開始。
2??對它調用我們之前學過的 siftDown (下沉) 操作。
siftDown的作用是，假設一個節點的左右子樹都已經是合法的堆，它可以讓這個節點“下沉”到正確位置，從而使這個節點和它的子樹共同構成一個更大的合法堆。
當我們從最后一個非葉子節點開始時，它的孩子必然是葉子節點（也就是合法的堆），所以 siftDown 的前提條件滿足了！
3??然后，我們向前移動到倒數第二個非葉子節點，對它也執行 siftDown。
因為我們是自底向上處理的，所以當處理這個節點時，它的子樹也必然已經被我們調整成合法的堆了。
4??我們不斷地向前重復這個過程，直到處理完根節點（下標為0）。當根節點也 siftDown 完畢后，整個數組就變成了一個合法的堆。
用一個實例來推演
我們用 arr = [3, 5, 80, 100, 70, 60] (n=6) 來走一遍這個流程。
-
非葉子節點的索引范圍是
0到(6/2) - 1 = 2。所以我們只需要處理索引2,1,0。 -
初始狀態：
3/ \5 80/ \ /100 70 601. 從 i = 2 (值為80) 開始:
-
對節點
80執行siftDown。 -
它的孩子是
60。80 >= 60，滿足堆序，無需交換。 -
數組狀態:
[3, 5, 80, 100, 70, 60] -
樹狀態 (局部)：
80/60 (這個小堆是OK的)2. 處理 i = 1 (值為5) :
-
對節點
5執行siftDown。 -
它的孩子是
100和70。 -
5小于它的更大的孩子100。 -
交換
5和100。 -
數組狀態:
[3, 100, 80, 5, 70, 60] -
樹狀態 (局部)：
100/ \5 70 (這個中等大小的堆也OK了)3. 處理 i = 0 (值為3，根節點) :
-
對節點
3執行siftDown。 -
它的孩子是
100和80。 -
3小于它更大的孩子100。 -
交換
3和100。 -
數組狀態:
[100, 3, 80, 5, 70, 60] -
3下沉到了原先100的位置（索引1）。現在要繼續對它進行siftDown。 -
節點
3(在索引1) 的新孩子是5(索引3) 和70(索引4)。 -
3小于它更大的孩子70。 -
交換
3和70。 -
數組狀態:
[100, 70, 80, 5, 3, 60] -
3下沉到了索引4，成為了葉子節點，siftDown結束。 -
最終樹狀態：
100/ \70 80/ \ /
5 3 60至此，整個數組已經是一個合法的大頂堆了。
第三步：編寫代碼
這個過程的代碼實現非常簡潔。它只需要一個 for 循環，從最后一個非葉子節點開始，調用我們已經寫好的 siftDown 函數。
// 假設我們有一個數組 arr 和它的長度 n
// 我們可以復用之前的 siftDown, 但需要稍微修改一下，讓它接受數組和范圍
void siftDownForSort(int arr[], int n, int index) {int currentIndex = index;while (leftChild(currentIndex) < n) { // 注意這里的邊界是 nint largerChildIndex = leftChild(currentIndex);int rightChildIndex = rightChild(currentIndex);if (rightChildIndex < n && arr[rightChildIndex] > arr[largerChildIndex]) {largerChildIndex = rightChildIndex;}if (arr[currentIndex] >= arr[largerChildIndex]) {break;}swap(&arr[currentIndex], &arr[largerChildIndex]);currentIndex = largerChildIndex;}
}// 我們需要 siftDown, swap, leftChild, rightChild 這些我們已經寫好的輔助函數
// ... (此處省略這些函數的代碼)// buildHeap 函數：將一個任意數組轉換成一個堆
// arr: 指向數組的指針
// n: 數組中元素的數量
void buildHeap(int arr[], int n) {// 找到最后一個非葉子節點的索引int lastNonLeafNode = (n / 2) - 1;// 從最后一個非葉子節點開始，自底向上，對每個節點執行 siftDownfor (int i = lastNonLeafNode; i >= 0; i--) {// siftDownForSort 函數就是我們之前為堆排序寫的 siftDown// 它接受數組、數組大小和要操作的索引作為參數siftDownForSort(arr, n, i); }
}總結與分析
我們通過兩種不同的思路來解決“建堆”問題：
-
方法一（自頂向下）：通過 N 次
insert(sift up)，時間復雜度為 O(NlogN)。 -
方法二（自底向上）：通過約 N/2 次
siftDown，時間復雜度為 O(N)。
雖然看起來都是循環N次，每次調用一個看似 O(logN) 的操作，但對于方法二，可以進行更嚴謹的數學分析：
大部分節點的 siftDown 操作都發生在樹的底層，路徑很短，只有根節點附近的少數節點才需要較長的 siftDown 路徑。所有操作的成本累加起來，總的時間復雜度其實是線性的 O(N)。
因此，自底向上的 siftDown 方法是構建堆的標準、最高效的算法。 它完美地體現了算法設計的智慧：通過改變看問題的角度，找到一個更深刻的結構性規律（葉子節點天然是堆），從而設計出更優的解決方案。
