第7章 堆積與圖結構#

本章目標#

• 實作二元堆積與 heap sort，理解優先權佇列的引擎。
• 掌握圖的三種表示法及其取捨。
• 實作併查集（Union-Find），學會路徑壓縮與按秩合併。

章前言#

本章把兩個看起來無關、實則都與「集合的組織方式」密切相關的主題放在一起：堆積與圖。

二元堆積（binary heap） 是第3章優先權佇列的引擎。它是一棵「形狀固定」的完全二元樹——永遠一層層填滿，因此可以用陣列表示而不需要任何指標；再靠「父不小於子（最大堆積）」的次序性質，讓「取最大值」變成 O(1)、「插入/刪除」變成 O(log n)。它不像 BST 那樣支援任意搜尋，但對「只要最值」的場景效率極高，而且就地排序（heap sort）也從它而來。

圖（graph） 則是描述「任意兩兩關係」的最一般化結構：地圖上的城市與道路、社群網路的人與好友、課程之間的先修關係。陣列描述「排成一列」，樹描述「階層」，圖描述「任意連接」——樹其實是無環圖的特例。本章先建立圖的表示法（相鄰矩陣、相鄰串列），為第9章的圖演算法鋪路。

併查集（Union-Find） 是管理「一堆元素分成幾組、查誰跟誰同組」的輕量結構，配合路徑壓縮與按秩合併後，單次操作近乎 O(1)，是 Kruskal 最小生成樹、社群連通性判斷的幕後功臣。它體現了一個深刻道理：有些問題不需要完整資訊，只需要「同組與否」，結構可以因此簡化到極致。