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。