這頁把兩種長得像樹、卻各解不同麻煩的結構擺在一起。想像急診室永遠先叫最危急的病人——Min-Heap(最小堆積)就是這種「隨時吐出當下最小值、又能一直塞新資料」的排隊器。另一邊,手機打「ca」就跳出 cat、car,是因為開頭相同的詞被疊起來共用同一段路徑,這正是 Trie(字典樹):查一個詞只跟它多長有關,跟字典收了幾萬個詞無關。下面你會看到堆積的上浮/下沉,與字典樹沿共享前綴逐字點亮。
兩者都是樹狀結構,但解決完全不同的問題:Min-Heap 是一棵完全二元樹、實際上以陣列存放(索引 i 的子節點固定為 2i+1 / 2i+2),只維持「父 ≤ 子」的局部堆積性質,換來 insert(上浮)/ extract(下沉)皆 O(log n) 的最小值存取; Trie 則是一棵共享前綴的多叉樹,每個節點代表一個字元、詞尾節點額外標記,插入與查詢都只需沿路徑走 O(m)(m=字串長度), 與詞典裡有幾個詞無關。
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(word) 從 root 逐字元走,該字元的子節點不存在就新建,走完後把當前節點標記為詞尾(isEndOfWord); 因此插入 'cat' 之後再插入 'car',兩者會共享 c→a 這段路徑,只在 't'/'r' 處分岔。search(word) 與 startsWith(prefix) 共用同一個 findNode:逐字元走 children,任一字元不存在就中途斷回傳「不存在」;search 走完後還要求該節點 isEndOfWord=true 才算命中(路徑存在但非詞尾要回傳 false),startsWith 只要走完(不論是否詞尾)就回傳 true。 本頁圖結構固定(insert 階段只是在既有圖上逐步點亮路徑,圖本身不隨操作重建)。