← 回首頁

堆積與字典樹(Heap / Trie)

這頁把兩種長得像樹、卻各解不同麻煩的結構擺在一起。想像急診室永遠先叫最危急的病人——Min-Heap(最小堆積)就是這種「隨時吐出當下最小值、又能一直塞新資料」的排隊器。另一邊,手機打「ca」就跳出 cat、car,是因為開頭相同的詞被疊起來共用同一段路徑,這正是 Trie(字典樹):查一個詞只跟它多長有關,跟字典收了幾萬個詞無關。下面你會看到堆積的上浮/下沉,與字典樹沿共享前綴逐字點亮。

兩者都是樹狀結構,但解決完全不同的問題:Min-Heap 是一棵完全二元樹、實際上以陣列存放(索引 i 的子節點固定為 2i+1 / 2i+2),只維持「父 ≤ 子」的局部堆積性質,換來 insert(上浮)/ extract(下沉)皆 O(log n) 的最小值存取; Trie 則是一棵共享前綴的多叉樹,每個節點代表一個字元、詞尾節點額外標記,插入與查詢都只需沿路徑走 O(m)(m=字串長度), 與詞典裡有幾個詞無關。

1. Min-Heap 二元堆積(陣列實作 + 上浮/下沉)

insert(value) 把新值附加到陣列尾端,再從該索引開始 bubbleUp:與父節點 ((i-1)/2) 比較,子 < 父就交換並繼續往上, 直到不再需要交換或走到 root。extract() 取出陣列開頭(root,即最小值),把陣列最後一筆搬到 index 0、長度 -1, 再從 root 開始 bubbleDown:與左右子中較小者比較,若子 < 自己就交換並繼續往下,直到不再需要交換或走到葉節點。 堆積只保證「父 ≤ 子」這個局部性質——不像 BST 維持全序中序遞增,換來的是 insert/extract 皆嚴格 O(log n)。 本頁樹狀渲染(TreeRenderer)與下方陣列面板是同一個 state.array 的兩種視圖:樹節點 id 即陣列索引, 每一幀彼此保證一致。

固定示範腳本:insert(50) insert(30) insert(70) insert(20) insert(60) insert(10) extract() extract()。 依序 extract 應取出 10、20(min-heap,插入值中最小的兩個,等於獨立排序後的前兩筆)。

操作腳本

    交換次數:0 堆大小:0
    紅色(current)= 當前處理的索引;黃框(frontier)= 正在比較(或剛交換)的父子索引組。 下方陣列面板與樹是同一份 state.array 的雙視圖,索引與樹節點 id 一一對應,高亮同步。

    陣列面板(索引:值)

    已取出(extracted,累積)

    已執行操作紀錄

    2. Trie 字典樹(共享前綴 + Insert / Search / StartsWith)

    insert(word) 從 root 逐字元走,該字元的子節點不存在就新建,走完後把當前節點標記為詞尾(isEndOfWord); 因此插入 'cat' 之後再插入 'car',兩者會共享 c→a 這段路徑,只在 't'/'r' 處分岔。search(word) 與 startsWith(prefix) 共用同一個 findNode:逐字元走 children,任一字元不存在就中途斷回傳「不存在」;search 走完後還要求該節點 isEndOfWord=true 才算命中(路徑存在但非詞尾要回傳 false),startsWith 只要走完(不論是否詞尾)就回傳 true。 本頁圖結構固定(insert 階段只是在既有圖上逐步點亮路徑,圖本身不隨操作重建)。

    固定示範腳本:insert('cat') insert('car') insert('card') insert('dog') → search('car')[找到] search('ca')[路徑存在但非詞尾] startsWith('ca')[有此前綴] search('cow')[中途斷,c 之後無 'o' 子節點]。

    操作腳本

      字元步數(charSteps):0
      節點上方文字 'w' = 該節點是某個詞的詞尾標記;紅色(current)= 當前處理的字元節點; 綠色(visited)= 本次 insert 或查詢已走過的路徑;深綠粗框(finalized)= 本次操作確認命中的詞尾節點。

      查詢結果

      (尚無查詢結果)

      已插入詞(累積)

      已執行操作紀錄