5.2 Topological sort、heap 與 Huffman coding

最後一份 CSCI2520 tutorial 把三個看似分開的題目放在一起：topological sorting、heaps、Huffman coding。它們的共同點是每一個問題都有明確的 structural constraint。

• Topological order 必須尊重所有 directed prerequisite edges。
• Heap 同時要滿足 shape condition 和 heap-order condition。
• Huffman tree 會反覆合併兩個最低 frequency 的部分。

Topological order

DAG condition 是必須的。若有 directed cycle，每個 vertex 都要在下一個之前， 繞一圈後就等於要求某 vertex 在自己之前，這不可能。

Kahn's algorithm

Kahn's algorithm 反覆選擇沒有 incoming edges 的 vertex，output 它，然後移除 它的 outgoing edges。安全放在最前面的 vertices，正是那些 prerequisites 已 經全部滿足的 vertices。

DFS-based topological sorting

Tutorial 也給 DFS 方法：從 unvisited vertices 做 DFS，當某 vertex 的 DFS 完成時，把它加到 output list 的 front。Finishing time 重要，因為一個 vertex 應該排在它能 reach 的 vertices 前面。

Kahn's algorithm 從「沒有未完成 prerequisites」出發；DFS method 從「descendants 已完成」出發。

Heaps

Tutorial 給出 min heap 的基本成本：

• insert: O(log n);
• findmin: O(1);
• delmin: O(log n);
• $build_heap$: O(n).

Complete-tree structure 令 heap 可以用 array 緊密儲存；heap-order property 解釋了為甚麼 minimum 一定在 root。

Huffman coding

Huffman coding 使用 min heap，反覆合併兩個 least frequent symbols 或 subtrees。結果是一棵 binary prefix-code tree，讓 frequent symbols 有較短 codes。

Tutorial 的 frequency example 顯示 algorithm pattern：先 build heap，再 重複 delmin 兩次、建立 combined node、把新 node insert 回 heap。

Merging sorted lists

同一個 priority-queue idea 也可用於 merge 多個 sorted lists。兩個 lists 時， 比較兩個 heads 即可；很多 lists 時，我們要在所有 current heads 裡找最小， heap 可以有效維護這個 minimum。

練習

1. 解釋 Kahn's algorithm 和 DFS-based topological sorting 的差異。
2. 為甚麼 min heap 的 findmin 是 constant time？
3. 解釋 Huffman coding 為甚麼反覆合併兩個 smallest frequency nodes。