Learning Objectives
- 用父 (i - 1) / 2、子 2i + 1 與 2i + 2 的索引公式，在陣列上檢查堆積性質
- 寫出下沉（sift down），並說明「挖洞」寫法為什麼比交換少寫入陣列
- 比較逐一插入建堆與由下往上建堆的工作量，用逐層加總說明後者是 O(n)
- 寫出原地的堆積排序，說明它 O(n log n)、額外空間 O(1)
- 用例子說明堆積排序不穩定
手上已經有一整批資料
演算法軌第 15 課用堆積做優先佇列：資料一個一個進來，每次放入、取出都是 O(log n)。 這一課處理另一種情況：資料一開始就整批在手上，例如要排序的一個陣列、要找前幾名的一份成績單。這時候要回答兩個問題：
- 把一個任意的陣列整理成堆積，最少要花多少工夫？
- 能不能就在原本的陣列裡完成排序，不另外開空間？
答案分別是由下往上建堆（O(n)，比一個一個插入的 O(n log n) 少）和堆積排序（原地、O(n log n)）。 要看懂這兩件事，先回到堆積的實作：它其實只是一個陣列。
完全二元樹放進陣列
二元堆積的形狀是完全二元樹：每一層都填滿，最後一層從左邊開始放。這種形狀可以一層一層、由左到右編號，直接存在陣列裡，不需要指標：
| 關係 | 索引（從 0 開始） |
|---|---|
| 節點 i 的左子節點 | 2i + 1 |
| 節點 i 的右子節點 | 2i + 2 |
| 節點 i 的父節點 | (i - 1) / 2（整數除法） |
| 有子節點的位置 | 0 到 n / 2 - 1 |
| 葉節點 | n / 2 到 n - 1，大約一半 |
最大堆積的規則只有一條：每個父節點都大於或等於它的子節點（最小堆積相反）。
所以根 a[0] 是最大值，但兄弟之間、不同子樹之間沒有大小關係，堆積不是排好序的陣列。
下面的程式只用索引公式檢查一個陣列是不是最大堆積：只要看前 n / 2 個位置，各自和子節點比一次。
用索引公式檢查堆積性質
第一次檢查 [9, 7, 8, 3, 6, 5, 4, 1, 2]，每個父節點都比子節點大，是最大堆積。把最後一格改成 8 之後，它的父節點是 a[3] = 3，規則被破壞了。檢查到 i = 3 就能停下。
下沉：建堆和排序共用的操作
下沉（sift down）處理的情況是：位置 i 底下的兩棵子樹都已經是堆積，只有 a[i] 可能放錯了。做法：
- 找出比較大的子節點 c（右子節點存在而且更大，就選右邊）
a[i]已經大於等於a[c]：停下，以 i 為根的子樹已經是堆積- 否則把
a[c]往上搬，a[i]往下移到 c，回到第 1 步
每往下一層，比較 2 次；最多走到葉節點，所以是 O(高度)＝O(log n)。
演算法軌用「交換」寫下沉：每一層交換一次，交換要寫入陣列 3 次（借一個暫存變數）。
另一種寫法叫挖洞：先把要下沉的值拿起來放在 x，原本的位置就變成一個「洞」；
每一層把較大的子節點搬上來填洞，洞就往下移一層；最後把 x 放進洞裡。每一層只寫入 1 次。
GCC 附的 C++ 標準函式庫（libstdc++）裡，push_heap、pop_heap、make_heap 用的就是這種寫法。
挖洞寫法：子節點往上搬，最後才放下
根是 1，底下兩棵子樹已經是最大堆積。注意看：搬上來之後，同一個值會暫時出現兩次（例如兩格都是 9），因為原本那格是「洞」，等下一層的值搬上來或最後放下 x 才會被蓋掉。1 一路沉到索引 7，只寫入陣列 4 次。
兩種建堆方法
把一個任意的陣列整理成最大堆積，有兩種做法：
| 做法 | 怎麼做 | 每一步的距離 |
|---|---|---|
| 逐一插入 | 把 a[0..k-1] 當成已經建好的堆積，k 從 1 到 n - 1，讓 a[k] 往上浮 |
新元素的深度：最多浮到根 |
| 由下往上 | 葉節點本身就是堆積；k 從 n / 2 - 1 往前到 0，讓 a[k] 往下沉 |
節點的高度：最多沉到葉 |
兩種方法每一步都是 O(log n)，看起來一樣。關鍵在於大部分節點在下層： 完全二元樹最下面一層就佔了大約一半的節點。逐一插入時，這些下層節點離根最遠，往上浮的距離最長； 由下往上建堆時，它們是葉節點，根本不用動，要沉很多層的只有上面少數幾個。
下面兩個範例用同一組資料 1, 2, …, 15 建最大堆積。由小到大的資料對兩種方法都是最壞情況： 每個新插入的數都比前面全部大，一定浮到根；每個要下沉的數都比它底下全部小，一定沉到葉。
逐一插入：越晚插入的浮得越遠
最下層的 8 個數（k = 7～14）每一個都要從第 3 層浮到根，各浮 3 層，光這一層就 24。總共浮 34 層。
由下往上：只有少數節點要沉得遠
葉節點（索引 7～14）完全不用處理。k = 6、5、4、3 各沉 1 層，k = 2、1 各沉 2 層，只有根要沉 3 層，總共 11 層。兩種方法建出來的堆積不一樣（印出來比一比），但都符合最大堆積的規則。
逐層加總：為什麼是 O(n)
把剛才 15 個節點的樹一層一層算。深度 d 的那一層有 2ᵈ 個節點；樹高 3，深度 d 的節點最多往下沉 3 - d 層、最多往上浮 d 層：
| 深度 | 節點數 | 由下往上：最多沉幾層 | 小計 | 逐一插入：最多浮幾層 | 小計 |
|---|---|---|---|---|---|
| 0（根） | 1 | 3 | 3 | 0 | 0 |
| 1 | 2 | 2 | 4 | 1 | 2 |
| 2 | 4 | 1 | 4 | 2 | 8 |
| 3（葉） | 8 | 0 | 0 | 3 | 24 |
| 合計 | 15 | 11 | 34 |
兩邊的差別一目了然：逐一插入時，節點最多的那一層乘上最大的距離；由下往上時，節點最多的那一層乘上 0。
樹變大時的規律（同樣用由小到大的資料，也就是最壞情況，數字是程式實際算出來的）：
| n | 由下往上：總層數 | 逐一插入：總層數 |
|---|---|---|
| 15 | 11 | 34 |
| 31 | 26 | 98 |
| 63 | 57 | 258 |
| 127 | 120 | 642 |
| 1023 | 1013 | 8194 |
n = 2ʰ⁺¹ - 1（最後一層填滿）時，由下往上剛好是 n - log₂(n + 1)，永遠小於 n； 逐一插入剛好是 (n + 1) × (log₂(n + 1) - 2) + 2，大約是 n 乘上 log₂n 再少一點，n 越大差距越懸殊。 用一般的寫法：高度 h 的節點最多約 n / 2ʰ⁺¹ 個，每個最多沉 h 層，總和是 n × (1/4 + 2/8 + 3/16 + 4/32 + …)，括號裡的總和不超過 1，所以是 O(n)。 逐一插入的總和由最下面一層主導：約 n / 2 個節點各浮 log₂n 層，所以是 O(n log n)。
由下往上建堆是 Robert W. Floyd 在 1964 年發表的 Treesort 3 裡的做法；同一年 J. W. J. Williams 發表堆積排序，用的是逐一插入。
想一想：索引與建堆
一個有 20 個元素的堆積存在陣列裡（索引從 0 開始）。由下往上建堆時，第一個要處理（往下沉）的位置是哪一個？
以下程式用由下往上的方法把 [3, 9, 2, 1, 4, 5] 建成最大堆積，會印出什麼？
為什麼由下往上建堆比逐一插入快？
原地的堆積排序
有了建堆，排序只差一步。陣列 a[0..n-1]：
- 由下往上建成最大堆積，O(n)
end從 n - 1 往前到 1：把根a[0]（目前堆積裡的最大值）和a[end]交換。最大值就落在它排好後該在的位置； 堆積的範圍縮成a[0..end-1]，換上來的值讓它往下沉，O(log n)
陣列被分成兩段：前面是還在整理的堆積，後面是已經排好、越來越長的區段。整個過程只在原本的陣列裡交換，額外空間 O(1)； 時間是 O(n) + (n - 1) × O(log n) ＝ O(n log n)，而且最壞情況也是如此。
要由小到大排序卻用最大堆積，是因為每次取出的最大值要放到陣列尾端；用最小堆積的話，取出的最小值沒有地方放。
堆積排序不穩定
排序演算法穩定（stable）的意思是：兩個鍵相同的元素，排序後仍保持原本的先後順序。 例如成績單先依座號排好，再依分數穩定排序，同分的人會維持座號順序。
堆積排序不穩定：交換會讓元素跨過很遠的距離，例如根和最後一格交換，就直接越過中間所有元素。
下面用兩個陣列表示資料：key 是排序依據，tag 是標籤，交換時兩個陣列一起換。
排序前 2A 在 2C 前面、3B 在 3E 前面，排序後兩組都對調了。
如果需要穩定，可以改用合併排序（演算法軌第 7 課），或把原本的位置當作第二個比較鍵，讓所有鍵都不相同。
鍵相同的元素換了先後
第一階段建堆時，3B 被換到根；第二階段第一輪，根和最後一格交換，3B 直接越過 3E 跑到最後面。最後印出 1D 2C 2A 3E 3B：兩組同分的元素都換了先後。
想一想：堆積排序
堆積排序在第二階段每一輪做的事是？
關於堆積排序，下列哪一個敘述正確？
實作：最大堆積的下沉
建堆與排序的兩個迴圈已經寫好了，只缺 sift_down。完成它之後，程式會印出建好的最大堆積和排序結果。預期輸出在右邊；可以切換成你熟悉的語言。
重點整理
- 堆積是存在陣列裡的完全二元樹：左子 2i + 1、右子 2i + 2、父 (i - 1) / 2；前 n / 2 個位置有子節點，其餘是葉
- 下沉：子樹都是堆積、只有根可能放錯時使用，O(log n)；挖洞寫法每層只寫入一次
- 由下往上建堆從 n / 2 - 1 往前做下沉，總工作量是各層「節點數 × 高度」的總和，小於 n，所以 O(n)；逐一插入是 O(n log n)
- 堆積排序：建最大堆積，再反覆把根換到尾端、縮小堆積、下沉；O(n log n)、額外空間 O(1)、不穩定
下一課：Trie 字典樹。換一種完全不同的樹：節點不存值，依字串的字元一層一層分支，用來做前綴搜尋與自動完成。