Learning Objectives
- 說明堆積的性質，以及完全二元樹怎麼用陣列存（父 (i - 1) / 2、子 2i + 1 與 2i + 2）
- 追蹤放入時的往上浮、取出時的往下沉，說明兩者都是 O(log n)
- 說明由下而上建堆為什麼只要 O(n)
- 寫出堆積排序，說明它的時間與空間複雜度
- 使用 Python heapq、C++ priority_queue、Java PriorityQueue，分辨它們預設是最小堆積還是最大堆積
- 用大小為 k 的最小堆積找出前 k 大
每次都拿出最優先的那一個
急診室依病情輕重決定看診順序，不是依掛號先後；作業系統挑優先權最高的程式先執行；外送平台把最近的訂單先派出去。 這些情境有兩個共同點：資料不斷加入，而且每次都要拿出最優先的那一個。這種資料結構叫優先佇列（priority queue）。
用學過的工具做做看：
| 做法 | 放入 | 拿出最小值 |
|---|---|---|
| 沒排序的陣列 | O(1)（接在最後） | O(n)（要全部看一遍） |
| 排好序的陣列 | O(n)（要挪出位置） | O(1) |
| 二元搜尋樹（第 14 課，平衡時） | O(log n) | O(log n) |
| 堆積（heap） | O(log n) | O(log n)，只看不拿是 O(1) |
二元搜尋樹也做得到，但它維持的是「全部排好」，比需要的多。堆積只維持「最小的在最上面」，要求比較少，所以可以用一個普通的陣列存，程式也短得多。
完全二元樹放進陣列
最小堆積（min-heap）是一棵二元樹，滿足兩個條件：
- 形狀：是完全二元樹（complete binary tree），每一層都填滿，只有最下層可以不滿，而且由左往右排，中間不留空位
- 順序：每個節點都小於等於它的子節點，所以根是全部裡最小的
最大堆積（max-heap）反過來，每個節點都大於等於子節點，根是最大的。
因為形狀是完全二元樹，可以一層一層、由左到右把節點放進陣列，不需要指標，用索引算出父子關係（索引從 0 開始）：
| 要找 | 索引 |
|---|---|
| 節點 i 的父節點 | (i - 1) / 2（整數除法） |
| 節點 i 的左子節點 | 2i + 1 |
| 節點 i 的右子節點 | 2i + 2 |
例如陣列 [1, 3, 5, 9, 8, 6]：索引 1 的 3，子節點是索引 3 的 9 和索引 4 的 8；索引 5 的 6，父節點是 (5 - 1) / 2 = 2，也就是 5。
注意堆積不是排好序的陣列。它只保證父節點比子節點小，兄弟之間、不同分支之間沒有大小關係（上面的 9 在 8 前面）。 n 個節點的完全二元樹高度約 log₂n，接下來的往上浮、往下沉最多走一條從根到葉的路，所以都是 O(log n)。
放入：接在最後面，再往上浮
依序放入 5、8、3、9、1、6。新元素先接在陣列最後面，也就是樹最下層最右邊的空位，這樣形狀仍然是完全二元樹；接著和父節點比，比父節點小就交換，一路往上浮，直到父節點比它小或到了根。放入 1 時交換了 2 次，一路浮到根。
取出：最後一個搬到根，再往下沉
最小值永遠在根 a[0]，看一眼是 O(1)。要把它拿走，就得補上根的空位，而且形狀要維持完全二元樹：
- 記下根的值（等一下要回傳）
- 把陣列最後一個元素搬到根，刪掉最後一格；形狀沒問題了，但新的根很可能太大
- 往下沉：和兩個子節點裡比較小的那個比，自己比較大就交換，一路往下，直到比兩個子節點都小或到了葉節點
第 3 步為什麼一定要選比較小的子節點？換上來的那個會變成另一個子節點的父節點，它必須比另一個子節點小，堆積的性質才成立。
取出最小值三次
從上一個範例建好的堆積 [1, 3, 5, 9, 8, 6] 連續取出三次。第一次取出 1 之後，6 被搬到根，和 3、5 裡比較小的 3 交換；再和 9、8 裡比較小的 8 比，6 比較小，停下來。取出的順序是 1、3、5，由小到大。
想一想：堆積的形狀與上下移動
下列哪一個陣列是最小堆積？
用 0 開始的索引，索引 10 的父節點是幾號？索引 4 的兩個子節點是幾號？
在最小堆積 [1, 3, 5, 9, 8, 6] 放入 0，放完之後陣列是什麼？
一次建好整個堆積：由下而上
手上已經有一整個陣列，要把它變成堆積，最直接的方法是一個一個放入，每次 O(log n)，總共 O(n log n)。 有更快的做法：由下而上建堆（bottom-up heapify），1964 年 Floyd 在發表的堆積排序程式（Treesort 3）裡用的就是這個方法。
- 葉節點自己就是一個合格的堆積，不用處理。索引 n / 2 之後全部是葉節點
- 從最後一個有子節點的位置 n / 2 - 1 開始，往前到 0，每個位置做一次往下沉
- 處理到位置 k 時，它底下的兩棵子樹都已經是堆積，往下沉之後以 k 為根的子樹也變成堆積
為什麼只要 O(n)？往下沉的距離最多是節點到葉的高度：大約一半的節點是葉子，沉 0 層；四分之一在倒數第二層，最多沉 1 層； 八分之一最多沉 2 層……越往上節點越少。把每層「節點數 × 最多沉幾層」加起來，總和小於 n。 一個一個放入則相反：多數節點在下層，往上浮的距離最長，所以比較慢。
由下而上建堆，數交換次數
9 個元素，k 從 3 往前到 0。k = 3 的 1 已經比子節點小，不用動；k = 0 的 9 一路沉到最下層，交換 3 次。總共只交換 6 次，比 9 個元素的 n log n 少很多。
堆積排序
堆積排序（heapsort）由 J. W. J. Williams 在 1964 年提出，同一篇文章也提出了二元堆積這個資料結構。做法分兩個階段：
- 把陣列建成最大堆積（由下而上，O(n)），最大值在
a[0] - 重複 n - 1 次：把
a[0]和堆積的最後一格a[end]交換，最大值就到了它該在的位置；堆積少一格，再讓新的根往下沉（O(log n)）
| 項目 | 堆積排序 |
|---|---|
| 時間 | 最好、最壞都是 O(n log n) |
| 額外空間 | O(1)，在原陣列裡排 |
| 穩定 | 不穩定（交換會跨越很遠的距離，相同的值可能換了先後） |
和第 07 課的合併排序比，堆積排序不需要額外陣列；和第 08 課的快速排序比，它沒有 O(n²) 的最壞情況。
實際上快速排序通常比較快（存取陣列的位置比較集中），所以 C++ 的 sort 常見的實作是以快速排序為主，遞迴太深時才改用堆積排序當保險。
堆積排序：最大值一個一個換到後面
前半段是建最大堆積，9 浮到 a[0]。後半段每一輪把 a[0] 換到 end 的位置，右邊排好的區域就多一格，再讓換到根的小值往下沉。注意這裡的 sift_down 是最大堆積：和比較大的子節點比。
三種語言的優先佇列
實際寫程式時不必自己寫堆積，三種語言都有內建的優先佇列，但預設方向不同，這是最容易出錯的地方：
| 語言 | 寫法 | 預設 | 放入／取出／看最前面 |
|---|---|---|---|
| Python | import heapq，用一般串列 |
最小堆積 | heappush(h, x)／heappop(h)／h[0] |
| C++ | priority_queue<int> |
最大堆積 | push(x)／pop()（不回傳值）／top() |
| C++ | priority_queue<int, vector<int>, greater<int>> |
最小堆積 | 同上 |
| Java | PriorityQueue<Integer> |
最小堆積 | add(x)／poll()／peek() |
需要相反方向時：
import heapq
h = []
for x in [3, 1, 4]:
heapq.heappush(h, -x) # Python 沒有最大堆積：存負數，取出時再變號
print(-heapq.heappop(h)) # 4
priority_queue<int> maxq; // C++ 預設就是最大堆積
priority_queue<int, vector<int>, greater<int>> minq; // 最小堆積要加 greater
PriorityQueue<Integer> maxq = new PriorityQueue<>(Comparator.reverseOrder()); // Java 最大堆積
依多個欄位決定優先順序時，Python 放元組 (優先度, 名稱)，依第一個欄位比、相同再比第二個；C++ 用 pair 或自訂比較；Java 傳 Comparator。
前 k 大是優先佇列最常見的用法：維持一個最多 k 個元素的最小堆積，每放入一個數，超過 k 個就把最小的丟掉。 最後留下的就是最大的 k 個，而根就是第 k 大。每次操作 O(log k)，n 個數總共 O(n log k)，比整個排序 O(n log n) 省，而且資料可以一邊讀一邊處理。
用內建優先佇列找前 3 名
三種語言分別用 heapq、priority_queue 加 greater<int>、PriorityQueue，都是最小堆積，輸出相同。堆積裡永遠只留目前最高的 3 個分數，根是其中最低的；放入 99 時，堆積超過 3 個，最小的 79 被丟掉。三種語言內部陣列的排列可能不同（取出時整理的細節不一樣），但取出的順序一定相同。
想一想：建堆、排序與內建工具
由下而上建堆時，為什麼從索引 n / 2 - 1 開始往前，而不是從 n - 1 開始？
以下 C++ 程式會印出什麼？
priority_queue<int> pq;
for (int x : {3, 1, 4, 1, 5}) pq.push(x);
cout << pq.top();
從 n 筆資料找前 k 大，用「最多 k 個的最小堆積」，時間複雜度是多少？
關於堆積排序，下列哪一個敘述正確？
實作：合併檔案的最小成本
有四個已經排好序的檔案，長度是 4、3、2、6。合併兩個長度 a、b 的檔案要花 a + b（第 07 課的合併）。每次都挑目前最短的兩個合併，總成本最小。請用最小堆積完成合併，印出每一次合併和總成本。預期輸出在右邊。
重點整理
- 堆積是完全二元樹，最小堆積的每個節點都小於等於子節點，根是最小值；只保證父子關係，不是排好序的陣列
- 用陣列存：父節點 (i - 1) / 2，子節點 2i + 1、2i + 2
- 放入：接在最後，往上浮；取出：最後一個搬到根，和較小的子節點交換往下沉；都是 O(log n)，看根是 O(1)
- 由下而上建堆從 n / 2 - 1 往前往下沉，只要 O(n)
- 堆積排序：建最大堆積，再把根一個一個換到後面；O(n log n)、額外空間 O(1)、不穩定
- 內建優先佇列：Python
heapq與 JavaPriorityQueue預設最小堆積，C++priority_queue預設最大堆積 - 前 k 大：最多 k 個的最小堆積，O(n log k)
下一課：圖的表示與 BFS。到了第 18 課的 Dijkstra 最短路徑，優先佇列會再派上用場：每次取出目前距離最近的節點。