← 回首頁

併查集/單調佇列/跳躍表（Union-Find / Monotone Queue / Skip List）

這頁把三個看似不相干、其實都在「用一個小聰明把慢動作變快」的結構擺在一起。Union-Find（併查集）像在一大群人裡快速回答「你們兩個是不是同一國」——順著「你老大是誰」一路問到頭就知道；單調佇列像排隊比誰最強，後面來了更強的，就把前面打不過的先請出隊，讓隊頭永遠是當下最大；Skip List（跳躍表）像翻字典時先靠側邊凸起的標籤跳到大概位置，再逐層往下找，不必一頁一頁翻。三者的共通取捨都是：多花一點點記錄或隨機的心思，換來查詢從「慢慢走」變成「幾步就到」。下面三段各有可播放的動畫，帶你看它們怎麼一步步取巧。

三個常被歸為「資料結構雜項」但各自解決獨立問題的結構：Union-Find（併查集）以森林 + 路徑壓縮 + 按秩合併， 近常數攤銷維護「誰跟誰同一組」；單調佇列以一個內部值嚴格遞減的雙端佇列，均攤 O(1) 回答固定大小滑動視窗內的最大值； Skip List（跳躍表）以多層鏈結、每層越高節點越稀疏，換取期望 O(log n) 的有序查找而不需 AVL/紅黑樹的旋轉邏輯。

本頁 Union-Find 用固定操作腳本逐步展示合併與路徑壓縮；若想看併查集在圖論演算法中被拿來加速批次查詢的實戰場景 → LCA 最近共同祖先對照（Tarjan 離線 LCA 用 Union-Find 加速批次根查詢）
Union-Find 另一個經典應用是 Kruskal 最小生成樹（排序邊後用 Union-Find 判斷兩端點是否已連通，已連通則跳過該邊以避免成環） → 進階圖論 Prim MST/Tarjan SCC（該頁示範的是另一種 MST 解法 Prim，用優先佇列貪心而非 Union-Find 判環）

1. Union-Find 併查集（路徑壓縮 + 按秩合併）

find(x) 沿 parent 指標走到根（parent[x]==x），回溯時把沿途每個節點的 parent 直接指向根（路徑壓縮），下次查詢同一節點就是 O(1)。 union(x, y) 先各自 find 出根，若不同根就依 rank（樹高上界的估計值）決定掛載方向：rank 小的掛到 rank 大的下面， 相同則固定把 rootY 掛到 rootX 下並將 rootX.rank 加一（按秩合併）。兩個優化合併使用時，m 次操作的攤銷成本為 O(α(n)) （反阿克曼函數，實際遠小於 5，近乎常數）。

固定示範腳本（n=8，兩排各 4 個節點）：union(0,1) union(2,3) union(0,2) union(4,5) union(6,7) union(4,6) union(3,7) find(1) find(5)——刻意先造出兩棵較深的樹，再由 union(3,7) 合併與後續 find 觸發路徑壓縮。

操作腳本

    find 呼叫次數：0 連通分量數（count）：8
    邊方向為 child → parent（自環／根節點不畫邊）；紅色（current）= 當前處理節點；綠色（visited）= 本次 find 走過的鏈；黃框（frontier）= union 正在比較的兩個根；深綠（finalized）= 本次合併後的新根。 節點上方文字 r=rank 只在該節點是根時顯示。下方陣列面板與圖是同一份 state.graph／parent 的兩種視圖，同一幀高亮同步。

    parent 陣列面板（索引:parent 值）

    ranks（節點:rank）

    本幀路徑壓縮

    （本幀無路徑壓縮）

    已執行操作紀錄

    Union-Find 只支援合併與查詢（不可刪邊、不可換根）；Link-Cut Tree 額外支援動態刪邊（cut）與換根（makeRoot）， 代價是用攤銷 O(log n) 的 splay tree 森林取代 Union-Find 攤銷 O(α(n)) 的路徑壓縮森林 → 費氏堆與 Link-Cut 樹

    2. 單調佇列（滑動視窗最大值，Monotone Queue）

    維護一個只存索引、對應值由前到後嚴格遞減的雙端佇列（deque）。掃描到索引 i 時，先把已滑出視窗左界（< i-k+1）的隊首彈出， 再把隊尾所有「值 ≤ nums[i]」的索引彈出（它們不可能再成為未來視窗的最大值），最後把 i 入隊尾；視窗形成後（i ≥ k-1）， 隊首索引對應的值即為當前視窗最大值。每個元素入隊、出隊至多各一次，均攤 O(1)，優於暴力每視窗掃描 O(k)。

    固定示範資料：nums=[4,3,5,1,2,6,2,7]，k=3（視窗大小 3）。逐一掃描 i=0..7， 視窗形成後的最大值序列（獨立驗算）：[5,5,5,6,6,7]。
    deque 操作次數（入隊+出隊，ops）：0
    藍框（cursor）= 當前索引 i；橘色（checking）= 目前 deque 內的索引；淡出的長條 = 目前視窗（range）之外；綠色（found）= 本幀讀出的視窗最大值所在索引。

    deque 內容（索引:值，隊首 → 隊尾）

    maxes（已解出的視窗最大值，累積）

    已執行操作紀錄

    3. Skip List 跳躍表（固定種子多層鏈）

    search/insert 皆從 head 出發，從目前最高層向右掃描：同層內只要下一個節點的值仍小於 target 就前進，走不動了就降到下一層繼續， 降到最底層（第 0 層）比對是否等於 target。insert 額外用亂數（本頁見下方誠實標示）決定新節點的層高，層數愈高機率愈低， 平均而言每層節點數約為下層的一半，因此期望查找/插入為 O(log n)——不需要 AVL/紅黑樹的旋轉邏輯，以「隨機層高」換取近似平衡。

    誠實標示：本頁層高由固定種子 LCG（線性同餘產生器）決定，而非真隨機——目的是讓示範可重播、逐幀可預測 （同 QuickSelect 頁固定種子的教學慣例）。實務上的 Skip List（如 Redis 有序集合底層）應使用真隨機亂數決定層高。

    固定示範腳本：insert(3) insert(6) insert(7) insert(9) insert(12) insert(19) → search(9)[命中] search(10)[未命中]。 固定種子（seed=1）算出的層高依插入序為 [4,4,2,1,2,1]，涵蓋 1/2/4 三種高度、兩座塔頂到層 4，足以展示跨層跳躍與降層。

    操作腳本

      橫向跳躍次數（hops）：0
      由上而下每列為一層（L{層數-1} 在最上，L0 為最底、包含所有節點）；橘色（current）= 當前掃描位置（單一層、單一節點）； 綠色（visited）= 本次操作已跳躍走過的節點。insert 完成宣告幀例外：橘色會整座新塔（跨其所有層）一起亮，代表剛插入的 節點串接進這些層。層高由固定種子決定（教學可重播），實務應為隨機。

      本次操作走訪路徑（path，層:值）

      本幀 insert 層高（levelOf）

      —

      本幀 search 結果

      —

      已執行操作紀錄

      Skip List 以隨機層高換取近似平衡；對照另一種完全不同的平衡策略——靠旋轉維持「左小右大」全序的二元搜尋樹 → 二元搜尋樹 BST/AVL
      Skip List 的「多層、越高越稀疏、跳得越遠」用在一維有序資料上；把同一套多層跳躍結構搬到多維向量空間、 每層改用貪婪圖走訪找近鄰，就是向量資料庫用來做近似最近鄰搜尋的 HNSW → 近似最近鄰 HNSW