Phase 02 — Data Structures（Day 11–20）

What：Array 是一段在記憶體中連續配置、每個元素大小相同、可用 index 直接定址的資料結構。「連續配置＋固定元素大小」是它所有特性（無論優勢或限制）的根源。

Internal Structure：第 k 個元素的記憶體位址 =base_address + k * element_size。因為每個元素大小相同且緊鄰排列，這個公式永遠成立，這就是 index 存取為何是 O(1) 的全部原因——它不是「查表」也不是「跳過去」，是直接算出來的。多數語言的「動態陣列」（Python list、Java ArrayList、Go slice、C++ vector）底層仍然是一段連續記憶體，只是實際配置的容量（capacity）大於目前使用的長度（length），多留的空間讓 append 不必每次都重新配置整段記憶體。

Core Operations：- Access by index：O(1)——直接用上面的公式算位置。- Search（未排序）：O(n)——沒有任何捷徑可跳過任何一個元素。- Search（已排序）：O(log n)——binary search，靠 index 隨機存取才有意義（Linked List 就算排序好也做不到 O(log n) search，因為找中點本身要 O(n)）。- Insert / Delete at end：平均（攤銷）O(1)，見下方 Resize 分析。- Insert / Delete at middle 或 front：O(n)——必須把插入點之後（或刪除點之後）的所有元素往後（或往前）搬移一格，維持「連續、無空隙」的不變量。

動態陣列擴充（Resize）的攤銷分析：當陣列已滿還要再 append 一個元素時，動態陣列會：(1) 配置一塊新的、容量通常是原本兩倍的連續記憶體；(2) 把舊陣列所有元素複製過去；(3) 釋放舊陣列，之後的 append 才真的寫進新配置的空間。單次觸發 resize 的那次操作是 O(n)，但這種情況平均每 n 次 append 只發生一次；把 n 次 append 中所有 resize 的複製成本加總（1 + 2 + 4 + ... + n ≈ 2n），除以 n 次操作，平均每次操作只分攤到 O(1) 的成本——這就是「攤銷 O(1)」的意思：不是每次都真的是 O(1)，是長期平均下來是 O(1)，代價是偶爾會有一次明顯比較貴的操作。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| Access by index | O(1) || Search（未排序） | O(n) || Search（已排序，binary search） | O(log n) || Insert/Delete at end | 攤銷 O(1) || Insert/Delete at middle/front | O(n) |

Strength：O(1) random access；記憶體連續配置讓 cache locality 極好——CPU 讀取記憶體時會一次預抓一整條 cache line，Array 相鄰元素大機率已經被一起載入 cache，實務上即使理論複雜度相同，Array 走訪往往比指標追蹤的結構快上數倍。

Weakness：中間位置的插入/刪除代價高（O(n) 搬移）；容量固定或需要 resize 時有一次性的搬遷成本；如果事先不知道資料量，過度保守配置會浪費記憶體、配置不足又會觸發多次 resize。

Typical Problems：Two Pointers、Sliding Window、Prefix Sum、原地反轉/旋轉（in-place reversal/rotation）——這些 pattern（Phase 03 會深入）全部建立在「O(1) random access」之上，沒有這個前提，這些技巧都無法用常數額外空間完成。

Backend Applications：連線池（connection pool）用固定大小的 slice/array 存放活躍連線；資料庫的 page 內部本質上是固定大小 slot 的陣列；分頁（pagination）用 LIMIT/OFFSET 時，OFFSET 的語意就是「陣列的第幾格開始」，這也是為什麼資料量大時 OFFSET 分頁會變慢（資料庫仍要數過前面所有列才能定位，等同陣列的線性特性在磁碟上的延伸）。

What：String 是字元組成的序列，可以視為 Array 的特化版本（元素類型固定為字元），多數語言底層用一段連續的 byte 或 code point 陣列儲存。

Internal Structure：兩個關鍵設計選擇決定了字串的行為：(1)編碼：Go 的 string 底層是 byte slice（UTF-8 編碼），用 index 存取拿到的是一個 byte，非 ASCII 字元（例如中文）會佔多個 byte，逐 byte 存取不等於逐字元存取，直接 s[i] 可能切到一個多位元組字元的中間；Python 3 的 str 則是 Unicode code point 序列，s[i] 保證拿到完整一個字元，但語言要在底層額外維護「code point → 記憶體位置」的對應（視內部編碼寬度而定）。(2) Immutability：多數語言（Java、Python、Go、JavaScript）的字串一旦建立就不可變，任何看似「修改」字串的操作（拼接、取代）實際上都是配置一段全新記憶體、複製舊內容加新內容，原本的字串物件本身完全沒被動到。

Core Operations：- Access by index：O(1)（byte 陣列語言中，注意這是 byte 不是字元，見上）。- Concatenation：單次 s1 + s2 是 O(n+m)（配置新記憶體、複製兩段內容）；在迴圈裡重複 s += x 執行 n 次，每次都要複製整個「目前已經有多長」的舊字串，總成本是 1+2+...+n ≈ O(n²)，而不是直覺以為的 O(n)。- Substring：多數現代語言是 O(k)（k 為子字串長度），需要複製一份新記憶體（少數語言的舊版實作曾經共享底層陣列做到 O(1)，但這會導致「小的子字串佔住整個大字串的記憶體無法釋放」的記憶體洩漏問題，因此現代主流實作已改為複製）。- Compare：O(n)——逐字元比較，除非字串本身有快取 hash 值（如 Java String 的 hashCode 欄位，第一次算過就快取起來）。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| Access by index | O(1)（注意 byte vs 字元的落差） || 單次 Concatenation | O(n+m) || 迴圈內重複 Concatenation（n 次） | O(n²) || Substring | O(k) || Compare | O(n) |

Strength：語意清楚、標準函式庫支援完整；immutable 帶來 thread-safety——多個執行緒同時讀同一個字串完全不需要加鎖，因為沒有任何操作能真的修改它。

Weakness：immutable 意味著任何「修改」都要重新配置記憶體，迴圈拼接因此有 O(n²) 陷阱；多位元組編碼下，逐 byte 的 index 操作容易產生把字元切一半的 bug（例如對中文字串做固定 byte 長度截斷，可能切出無法解碼的殘缺字元）。

Typical Problems：Substring search（Phase 03 會深入 KMP/Rabin-Karp）、Palindrome check、Anagram 判斷（常搭配 HashMap 計數字元出現次數）、大量拼接時改用 builder pattern（如 JavaStringBuilder、Go strings.Builder）取代 +=。

Backend Applications：SQL 查詢語句組裝——禁止用字串拼接把使用者輸入直接接進 SQL（同時踩到效能與安全性兩個問題：immutable 拼接的複製成本、以及 SQL Injection 風險），必須用 parameterized query；高頻路徑的 log 訊息組裝應使用 builder 而非 +=，避免在高 QPS 下產生大量短命的中繼字串物件、增加 GC 壓力；HTTP body 在[]byte 與 string 之間轉換也有複製成本，高吞吐服務會盡量減少不必要的轉換次數。

What：HashMap（也稱 Hash Table、Dictionary）是一種用 key 直接算出儲存位置、達到平均 O(1) 存取的資料結構。本質是「Array ＋ Hash Function」的組合：底層仍然是一段連續配置的陣列（bucket array），Hash Function 負責把任意型別的 key 轉換成這個陣列的一個合法 index。

Internal Structure（依內部規劃文件「特別深入」段落逐項展開¹）：

• Hash function：把 key 轉成一個整數（hash code），再對 bucket array 的長度取模（hash(key) % bucket_count）得到實際存放的 index。一個好的 hash function 要讓不同 key 的 hash 值均勻分布，避免大量 key 集中落在同一個 bucket。
• Bucket：bucket array 裡每一格稱為一個 bucket。因為多個不同的 key 有機會 hash 到同一個 index（見下），一個 bucket 實際上可能同時存放 0 筆或多筆資料。
• Collision：兩個不同的 key 經過 hash 與取模後落到同一個 bucket index，稱為碰撞（collision）——即使 hash function 設計得再好，只要 key 的數量夠多、bucket 數量有限，碰撞在數學上是必然會發生的（鴿籠原理）。常見的兩種解法：1. Separate chaining：每個 bucket 存一個 linked list（或資料量大時退化成小型樹），碰撞的 key 全部掛在同一條 list 上；查詢時先用 hash 算出 bucket index，再走訪該 bucket 的 list 逐一比對 key 找到正確的那筆。2. Open addressing（如 linear probing）：碰撞時不额外配置 list，而是依規則往後尋找下一個空的 slot 存放；查詢時也依同樣規則往後找，直到找到相符的 key 或遇到一個空 slot（代表 key 不存在）。
• Load factor：load factor = 元素數量 / bucket 數量，代表 bucket array 的擁擠程度。Load factor 越高，碰撞機率越高，每個 bucket 平均要比對的元素數也越多，效能會逐漸從 O(1) 退化向 O(n)。
• Resize：當 load factor 超過設定門檻（常見預設 0.75）時，HashMap 會配置一個更大（通常是兩倍）的新 bucket array，並把所有既有元素重新計算 hash、依新的 bucket 數量重新分配位置（rehash）——這一步是必要的，因為 index 是靠 hash(key) %bucket_count 算出來的，bucket_count 一旦改變，同一個 key 對應的 index 幾乎必然也會跟著改變，舊的擺放位置全部失效。

Core Operations：get(key) / put(key, value) /delete(key) / containsKey(key)——四者的機制完全相同：先算hash(key) % bucket_count 定位到 bucket，再視碰撞解法在該 bucket 內找到（或建立）正確的 entry。

Complexity：

| 情境 | 複雜度 ||---|---|| 平均情況（hash 分布均勻、load factor 受控） | O(1) || 最差情況（大量 key 碰撞到同一個 bucket） | O(n) |

最差情況並非只是理論假設——如果攻擊者能故意構造大量 hash 值相同的 key 送進一個公開接受使用者輸入當 key 的 HashMap（例如某些語言早期版本的 hash function 可被預測），可以把整個 HashMap 的操作拖到 O(n)，這稱為 hash flooding attack，是部分語言後來把預設 hash function 加上隨機種子（每次程式啟動不同）的原因之一。

Strength：平均 O(1) 的 get / put / delete，遠快於 Array 的線性搜尋，是「用任意 key 快速查值」場景的預設選擇。

Weakness：最差情況會因碰撞退化；resize 觸發時有一次性的 O(n) 搬遷成本，即使長期攤銷後仍是 O(1)，單一次操作仍可能踩到這個 O(n) 尖峰；沒有固定的遍歷順序（除非用 LinkedHashMap 等維護插入順序的變體）；記憶體開銷比 Array 大——bucket array 通常留有尚未使用的空位，加上 separate chaining 額外的 linked list node overhead。

Typical Problems：用 HashMap 做 O(1) 查找/去重（如 Two Sum）、計數（字元頻率、Anagram 判斷）、快取查找（LRU Cache 的 O(1) 查找部分，見 Day 14）、集合運算（交集/聯集靠底層是 HashMap 的 HashSet，見 Day 13）。

Backend Applications：Session store 用 user id 當 key 查 session 資料；快取系統（如 Redis）核心概念是分散式版本的 hash table；PostgreSQL 支援 Hash Index，直接對應這裡「用 hash 值定位」的原理（適合等值查詢，不支援範圍查詢，因為 hash 值不保留大小順序）；Rate limiter 用 client id 當 key 記錄該 client 目前的請求次數。

What：HashSet 是「只存 key、不存 value」的 HashMap——本質上是把 HashMap 的 value 型別固定成一個沒有意義的哨兵值（或直接省略 value 欄位），只利用 HashMap 的「key 唯一、O(1) 查找」能力來判斷「這個元素存不存在」。

Internal Structure：與 HashMap 完全相同的 bucket array ＋ hash function ＋ collision resolution（不少語言的標準函式庫實作，例如 Java 的 HashSet，內部就是包裝一個 HashMap，把每個加入的元素當作 key，value 統一塞一個共用的哨兵物件）。因此 Day 12 學到的 hash function / bucket / load factor / resize 全部原封不動適用在 HashSet 上。

Core Operations：add(element) / contains(element) /remove(element)，機制與複雜度與 HashMap 的 put / get /delete 完全相同。

Complexity：與 HashMap 相同——平均 O(1)，最差情況（大量元素碰撞）O(n)。

Strength：語意清楚（明確表達「這是一個集合」而不是「這是一個映射」）；O(1) 去重/查找；可以直接組合出數學上的集合運算——交集（遍歷較小的集合，逐一 contains 另一個集合）、聯集（把兩個集合的元素都 add 進第三個集合，重複元素自然只會被存一次）、差集（遍歷集合 A，只保留不在集合 B 裡的元素）。

Weakness：與 HashMap 完全相同——最差情況會退化、無序、resize 時有一次性尖峰成本；因為本質只是 HashMap 的特化用法，HashSet 沒有比 HashMap 更多的能力，改用 HashSet 純粹是語意上更精確，不是效能上的額外優化。

Typical Problems：陣列去重（distinct）、判斷陣列中是否存在重複元素、集合的交集/聯集/差集運算、圖走訪（BFS/DFS）時用來記錄「哪些節點已經走訪過（visited）」避免重複處理同一個節點。

Backend Applications：記錄已經處理過的訊息 id，避免同一則訊息被重複消費（是實作 idempotency 的其中一種簡易手段，完整的 idempotency 設計還需考慮持久化與過期，這裡只涵蓋記憶體內判斷存在與否的部分）；權限系統用 HashSet 存放一個使用者擁有的角色集合，用 O(1) 的 contains 判斷「這個使用者有沒有某個角色」；走訪服務依賴圖（找出循環依賴、拓樸排序）時用 visited set 避免重複走訪同一個服務節點。

What：Linked List 是一連串「節點（node）」透過指標（pointer /reference）串接起來的資料結構，每個節點存放資料本身與指向下一個節點的指標，節點彼此不要求在記憶體中連續。

Internal Structure：每個 node 包含 (data, next) 兩個欄位（Doubly Linked List 多一個 prev）；整個 list 只需要記住 head指標（若有維護 tail 指標，尾端操作也能加速，見下）。因為節點各自獨立配置在記憶體中的任意位置（不連續），走訪必須沿著 next指標一個一個跳過去，不像 Array 可以用算術公式直接算出第 k 個元素的位置。

Core Operations：- Access by index：O(n)——必須從 head 沿著 next 走 k 步，沒有任何算術捷徑可以跳過中間的節點。- Insert / Delete at head：O(1)——只需要改 head 指標本身。- Insert / Delete at tail：若有維護 tail 指標為 O(1)，否則要先走到底才能操作，退化成 O(n)。- Insert / Delete at 已知節點（手上已經有該節點的指標，例如走訪過程中）：O(1)——只需要改前後節點的指標，不需要搬移任何其他元素的資料。這是 Linked List 相對 Array 的核心優勢，前提是「已經定位到那個節點」；定位本身仍然是 O(n)，優勢只發生在「已經在那裡」之後的操作。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| Access by index | O(n) || Insert/Delete at head | O(1) || Insert/Delete at tail（有維護 tail 指標） | O(1) || Insert/Delete at 已知節點 | O(1) |

Strength：插入/刪除已知節點是 O(1)，不需搬移其他元素；大小可以彈性增長，不需要像 Array 一次性配置一整段連續記憶體，對「大小事先不確定」或「記憶體較零碎」的環境更友善。

Weakness：沒有隨機存取能力（找第 k 個是 O(n)）；每個節點都多了一份指標的記憶體開銷；節點分散在記憶體各處，cache locality 差——CPU 每次跳到下一個節點都可能是一次 cache miss。實務上即使理論複雜度看起來更好，Linked List 在現代硬體上經常反而比 Array 慢，因為一次 cache miss 的實際代價，遠高於「少搬幾個元素」省下的時間；這也是為什麼許多語言的標準函式庫在資料量不大時，仍傾向優先使用 Array 為底的結構。

Typical Problems：反轉 Linked List（迭代改指標方向）、判斷是否有環（Floyd's cycle detection，快慢指標）、找中間節點（快慢指標的另一個應用）、合併兩個已排序的 Linked List、LRU Cache 的雙向 Linked List 部分（見下方陌生題）。

Backend Applications：LRU Cache 是後端最常見的 Linked List 應用——用 HashMap 存 key → node 的對應做到 O(1) 查找，用 Doubly Linked List 維護存取順序，讓「把某個元素標記為最近使用」做到 O(1)（見下方陌生題完整推導）；訊息/任務佇列的底層有時用 Linked List 實作，方便在任一端便宜地插入/移除；資料庫的 undo log / redo log 有時用鏈結串列串接一連串的變更記錄，方便照順序回放或回溯。

What：Stack 是一種「後進先出（LIFO, Last-In-First-Out）」的資料結構，只能在同一端（稱為 top）做新增（push）與移除（pop）。

Internal Structure：可以用 Array（維護一個 top index，push 時 index 加一並寫入，pop 時讀出當前值後 index 減一）或 Linked List（永遠在 head 端 push/pop）實作，兩者都能讓 push/pop 做到 O(1)。用 Array 實作時，如果容量不足，會觸發跟 Day 11 動態陣列完全相同的攤銷擴充機制。

Core Operations：push O(1)、pop O(1)、peek（查看 top 但不移除）O(1)。Stack 刻意不提供隨機存取中間元素的操作——這是設計上的限制，用來保證「只能從一端進出」的語意不會被繞過。

Complexity：push / pop / peek 皆為 O(1)（若底層用 Array 實作，是攤銷 O(1)，因為可能觸發 resize）。

Strength：O(1) 的兩端操作；天然對應「巢狀」、「回溯」語意（函式呼叫棧、括號匹配、瀏覽器上一頁）。

Weakness：無法隨機存取中間元素；無法直接查詢「目前最小值」等聚合資訊，除非額外維護輔助結構（例如 min stack 用一個平行的輔助 stack 隨時記錄目前最小值）。

Typical Problems：括號匹配（valid parentheses）、逆波蘭表達式（RPN）計算、單調棧（monotonic stack，找下一個更大元素，Phase 03 會深入）、用顯式 stack 取代遞迴實作 DFS、undo/redo 功能。

Backend Applications：函式呼叫棧本身就是一個 Stack——每次函式呼叫會 push 一個 stack frame，return 時 pop 掉，這也是為什麼遞迴呼叫太深會發生 stack overflow；許多語言的 middleware/interceptor chain 用 stack 概念管理「進入時依序執行、離開時反序執行」（例如 Go 的 defer 機制本質上就是一個 stack：多個 defer會依「後宣告先執行」的順序跑）；分散式追蹤（tracing）中，span 的父子呼叫關係常用 stack 追蹤「目前執行在哪一層呼叫中」。

What：Queue 是一種「先進先出（FIFO, First-In-First-Out）」的資料結構，新增（enqueue）發生在一端（tail），移除（dequeue）發生在另一端（head）。

Internal Structure：若天真地用 Array 實作、在 index 0 做 dequeue，會需要把後面所有元素往前搬一格（O(n)）；實務上會改用環狀陣列（circular buffer）——維護 head 與 tail 兩個 index，dequeue 時只需要把 head index 往前移動一格（用取模繞回陣列開頭，例如 head = (head + 1) % capacity），完全不搬移任何資料。若改用 Linked List 實作（同時維護 head 與 tail 指標），enqueue 在 tail 端、dequeue 在 head 端，兩者都是 O(1) 改指標，不需要環狀邏輯，但代價是 Linked List 本身的 cache locality 較差（見 Day 14）。

Core Operations：enqueue O(1)、dequeue O(1)（前提是用環狀陣列或雙指標 Linked List 實作，天真的陣列搬移實作是 O(n)）、peek（查看最前面但不移除）O(1)。

Complexity：

| 實作方式 | dequeue 複雜度 ||---|---|| Naive array（dequeue 時整體往前搬） | O(n) || Circular buffer（環狀陣列） | O(1) || Linked List（維護 head/tail 指標） | O(1) |

這張表刻意強調：Queue 的複雜度不是資料結構本身決定的，是實作方式決定的——選錯實作方式（天真陣列搬移）會讓 Queue 整組操作退化成 O(n)，即使概念上 Queue「應該」是 O(1)。

Strength：正確實作（環狀陣列或 Linked List）前提下，兩端操作皆為 O(1)；天然對應「公平排隊」語意。

Weakness：與 Stack 相同，無法隨機存取中間元素；環狀陣列實作需要額外處理「陣列滿了要擴充」與「head/tail index 繞回陣列開頭」的邊界邏輯，寫錯容易出現 off-by-one 或「滿」與「空」兩種狀態難以區分（head == tail 時到底是空還是滿）的 bug，通常需要額外一個計數欄位或刻意保留一格不使用來消除歧義。

Typical Problems：BFS 用 Queue 維護待走訪節點（Day 14 已用過的圖走訪、樹的層序走訪）、任務排程（依 FIFO 順序處理）、滑動窗口（Sliding Window，Phase 03 會用到 Deque，這裡先用一般 Queue 鋪墊概念）、生產者-消費者模式的緩衝佇列。

Backend Applications：訊息佇列（RabbitMQ / Kafka 的基本語意都是 FIFO，雖然實務上會有 partition、priority 等變化打破嚴格 FIFO）；非同步任務佇列（background job queue），worker 依序 dequeue 處理任務；request buffering——在同時湧入的連線數超過處理能力時，先排隊而非直接拒絕；部分 rate limiter 的實作方式是用 Queue 存最近一段時間內請求的時間戳，判斷視窗內請求數是否超過限制。

What：Deque（double-ended queue）是兩端都能新增／移除的資料結構——同時擁有 Stack「兩端各自都能 push/pop」與 Queue「一端進一端出」的能力，把「只能操作固定端」的限制完全拿掉，任何一端都能pushFront / pushBack / popFront / popBack。

Internal Structure：延伸 Day 15 Queue 的兩種實作方式，差別在於兩端都要能操作：- 環狀陣列（circular buffer）：延伸 Day 15 的作法，head 與tail 兩個 index 都可以往前也可以往後移動（用取模讓 index 在兩個方向繞回陣列邊界），陣列滿了時的擴充機制與 Day 11 動態陣列相同。- Doubly Linked List：延伸 Day 14 的 prev/next 雙向指標，同時維護 head 與 tail 指標，任一端的 push/pop 都只需要改最多兩個節點的指標。

Core Operations：pushFront / pushBack / popFront /popBack / peekFront / peekBack，六者皆為 O(1)（環狀陣列版本是攤銷 O(1)，理由與 Day 11 動態陣列相同）。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| pushFront / pushBack | 攤銷 O(1) || popFront / popBack | O(1) || peekFront / peekBack | O(1) |

Strength：可以完全取代 Stack（只用一端）或 Queue（一端進一端出）的功能，是兩者的超集合；特別適合「候選視窗需要兩端都能移除」的演算法（monotonic deque）。

Weakness：與底層實作方式綁定的既有取捨仍然存在——環狀陣列版兩端都要處理 index 繞回陣列邊界的邊界邏輯（比單端的 Queue 多一倍的邊界情境要處理，off-by-one 風險更高）；Doubly Linked List 版仍然有 Day 14 提過的 cache locality 較差的問題。

Typical Problems：Sliding Window Maximum/Minimum——維護一個 monotonic deque（例如求最大值時，deque 內由頭到尾遞減排列）：新元素從尾端加入前，先把尾端所有小於等於新元素的候選都 pop 掉（它們不可能再是視窗內的最大值，因為新元素比它們晚離開視窗又比它們大）；視窗左邊界移動時，若 deque 頭端元素的 index 已經滑出視窗，從頭端 pop 掉。因為每個元素最多被 push 一次、pop 一次，整個過程總成本是 O(n)，遠比每次視窗移動都重新掃描視窗內全部元素找最大值（O(n·k)，k 為視窗大小）快；回文（palindrome）檢查也可以用 deque 從兩端同時取值比對。

Backend Applications：Sliding Window 限流演算法（Phase 05／07 會深入的 rate limiter 之一種實作方式）用 deque 存最近一段時間內的請求時間戳，兩端都需要移除（頭端移除過期的舊時間戳、尾端可能需要移除不再有效的候選）；部分語言 runtime 的 work-stealing scheduler（例如 Go runtime 每個 P 的本地 run queue）讓 owner 從一端存取（低成本、無競爭），其他閒置的 worker 從另一端「偷」工作，兩端各自有不同用途正是 Deque 語意的體現。

What：Heap 是一棵「完全二元樹（complete binary tree）」——除了最後一層，每一層都必須填滿，且最後一層由左至右依序填入不留空隙——並滿足 heap property：Max Heap 中每個父節點都 ≥ 子節點；Min Heap 相反，每個父節點都 ≤ 子節點。Priority Queue 是「每次都能取出優先權最高（或最低）的元素」這個抽象介面，Heap 是它最主流的具體實作。

Internal Structure：因為完全二元樹「除了最後一層都填滿、最後一層由左至右填」的規則，樹的形狀是完全確定的，不需要任何指標，可以直接用一個 Array 表示：0-indexed 陣列中，index i 的節點，其左子節點在 2*i + 1、右子節點在 2*i + 2、父節點在(i - 1) / 2（整數除法向下取整）。這個公式之所以永遠成立，正是因為 Array 本身「用 index 直接算出位置」的 O(1) 定址能力（Day 11）加上完全二元樹「不留空隙」的形狀規則——兩者缺一，這個算術關係都不成立。

Core Operations（依文件「特別深入」段落逐項展開，以 Min Heap 為例）：- Insert：把新元素放進陣列最後一個位置（樹的最底層、最右邊第一個空位，維持完全二元樹形狀），再「sift up（上浮）」：把它與父節點比較，若比父節點小就與父節點交換，重複這個比較－交換，直到不再違反 heap property 或到達 root。因為完全二元樹高度是O(log n)，sift up 最多走這麼多步，是 O(log n)。- Extract-Min：root（index 0）永遠是最小值，O(1) 就能讀到；但移除它需要維持完全二元樹形狀：把陣列最後一個元素搬到 root 位置、刪除原本最後一個位置，再對新的 root「sift down（下沉）」：與左右子節點中較小的那個比較，若新 root 更大就與它交換，重複直到不再違反 heap property 或到達葉節點。同樣因為樹高O(log n)，是 O(log n)。- Heapify（從 n 個元素直接建堆）：天真做法是逐一 Insert n 個元素，每次 O(log n)，總共 O(n log n)。更好的做法：把 n 個元素先全部塞進陣列（此時還不滿足 heap property），從「最後一個非葉節點」開始由後往前，對每個節點做一次 sift down。這樣做總成本是 O(n)，不是 O(n log n)——關鍵在於：完全二元樹裡，越靠近底部的節點數量越多，但底部節點的高度（到葉節點的距離）越小，sift down 的成本正是與節點高度成正比；把每一層「節點數量 ×該層高度」加總（n/4 * 1 + n/8 * 2 + n/16 * 3 + ...），這個級數收斂到 O(n)，不是把每個節點都當作 O(log n) 那樣天真估計（那是 Insert n 次的分析，不是由下往上 sift down 的分析）。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| Insert | O(log n) || Extract-Min/Max | O(log n) || Peek Min/Max | O(1) || Heapify（從 n 個元素直接建堆） | O(n) || 任意元素的 Search | O(n)（無捷徑，見 Weakness） |

Strength：O(log n) 的 insert / extract，O(1) 的 peek；heapify 是 O(n)，當只需要「重複取出最小/最大值」而不需要完整排序時，比先排序全部元素（O(n log n)）划算；用 Array 表示，不需要額外的指標記憶體開銷。

Weakness：無法有效搜尋任意元素——heap property 只保證「父子之間」的順序，同一層或跨子樹的元素之間沒有大小關係，要找特定值只能 O(n) 全部掃過；不維護全域排序，直接走訪陣列拿到的順序不是排序好的順序（要拿到排序結果得不斷 extract）；decrease-key（把某個已在堆中的元素的優先權調低/調高）不是天生 O(log n)——標準 Array-backed heap 沒有「已知某元素在陣列的哪個位置」的捷徑，要先花 O(n) 找到它，才能再花 O(log n) sift up/down 調整位置；Dijkstra 最短路徑演算法需要頻繁 decrease-key，這也是為什麼進階應用會改用額外維護「元素 → 陣列位置」對應的 indexed heap，或更複雜的 Fibonacci heap（本教材不要求手刻，只需知道這是一個真實存在的限制與對應解法）。

Typical Problems：Kth Largest/Smallest Element（維護一個大小為 K 的 heap，見下方陌生題完整示範）、Top K Frequent Elements（HashMap 計數＋大小 K 的 heap，Day 20 綜合練習會實作）、Median Maintenance（用一個 max-heap 存較小的一半、一個 min-heap 存較大的一半，兩個 heap 大小差距維持在 1 以內，median 就是其中一個 heap 的 root，或兩個 root 的平均）、Merge K Sorted Lists（heap 裡放 K 個 list 目前的最小候選，每次 extract 後把該 list 的下一個元素放入）、Dijkstra 最短路徑（每次取出目前已知距離最短的未定節點）。

Backend Applications：任務排程器用 heap 依「下次執行時間」或優先權挑出下一個要跑的工作（Phase 07 T-032 的 Job Scheduler 會再深入）；連線池/快取淘汰策略用 heap 找出「優先權最低」該被淘汰的項目；負載平衡器用 min-heap 依目前負載挑選要分派請求的伺服器；Kafka 等訊息系統的 consumer 在多個 partition 間追蹤「目前最小的未提交 offset」時，概念上就是在維護一個 min-heap 的語意。

What：Binary Tree 是由節點（node）組成的階層式資料結構，每個節點最多有兩個子節點（left、right），有一個唯一的 root 節點做為起點，是 Linked List「node + 指標」概念的推廣——差別在於 Linked List 每個節點只有一個 next，Binary Tree 每個節點有兩個子指標，形狀從「一直線」變成「可以分岔的階層」。

Internal Structure：每個節點包含 (data, left, right) 三個欄位，left/right 各自指向另一個節點或為空（null）。整棵樹只需要記住 root 指標。節點彼此不要求連續記憶體，走訪必須沿著指標移動（與 Linked List 相同的取捨：換取形狀彈性、犧牲 cache locality）。

Core Operations（Traversal，四種走訪順序）：- 前序（Pre-order）：root → left → right——先處理節點本身，再處理左子樹、右子樹。適合「複製整棵樹」或「先取得節點資訊再往下展開」的場景（例如把樹結構序列化成一份可以照原樣重建的紀錄）。- 中序（In-order）：left → root → right——先處理完左子樹，再處理節點本身，最後處理右子樹。對 BST 而言，中序走訪保證拿到嚴格遞增排序的輸出（見下方 BST 小節，這是 BST 最重要的性質之一）。- 後序（Post-order）：left → right → root——先處理完兩個子樹，最後才處理節點本身。適合「刪除整棵樹」（必須先刪光子節點才能安全刪除父節點）或「先算出子節點的值才能算出父節點的值」的場景（例如計算子樹大小、子樹高度）。- 層序（Level-order / BFS）：由上而下、同一層由左至右依序走訪。前三種都是「沿著一條路徑先走到底」的深度優先（DFS），自然適合用遞迴實作（呼叫堆疊本身就是一個隱式的 Stack，見 Day 15）；層序走訪則是廣度優先（BFS），需要顯式維護一個 Queue：從 root 開始入隊，每次取出一個節點處理，再把它的子節點依序入隊，直到 Queue 清空——這正是 Day 15 Queue「FIFO」語意的直接應用：先進的節點（較早那一層）保證先被處理完。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| 任一種 Traversal（走訪全部 n 個節點） | O(n) || Traversal 額外空間（遞迴/Stack 版本） | O(h)，h 為樹高 || Traversal 額外空間（層序/Queue 版本） | O(w)，w 為樹的最大寬度 |

Strength：能表達階層/分岔關係，是後面 BST、Trie、Graph 的共同基礎；四種走訪順序涵蓋大部分「處理階層資料」的需求（序列化、排序輸出、由下而上聚合、由上而下逐層處理）。

Weakness：普通 Binary Tree（沒有 BST 排序不變量）沒有 O(log n)搜尋能力，找特定值仍是 O(n)；遞迴走訪在樹很深時可能有 stack overflow 風險（呼叫堆疊本身是有限資源，見 Day 15 Stack 的 Backend Applications）。

Typical Problems：樹的序列化/反序列化（常用前序＋記錄 null 節點）、計算樹高/節點數（後序遞迴，子節點算完才能算父節點）、判斷兩棵樹是否結構相同、層序走訪輸出每一層的節點清單。

Backend Applications：檔案系統目錄結構、組織架構圖、UI 元件的階層結構（DOM tree）、決策規則/設定的階層繼承（子設定覆寫父設定）都是 Binary Tree（或其推廣為多元樹）的實例；DB 的 B-Tree 索引（Phase 04 深入）本質上也是這裡「階層式指標結構」概念的推廣，只是每個節點的子節點數遠大於 2。

What：BST 是在 Binary Tree 之上多加一條不變量（invariant）的特化版：對任何節點，其左子樹所有節點的值都小於它、右子樹所有節點的值都大於它（假設沒有重複值）。Balanced Tree 是在 BST 之上再多加「維持樹高在 O(log n)」的保證，AVL Tree、Red-Black Tree 是最主流的兩種具體實作。

Internal Structure：延續 Binary Tree 的 (data, left, right)節點結構，額外要求任何時刻都要維持「左小右大」的不變量。

Core Operations：- Search(value)：從 root 開始，若目前節點值等於目標，找到；若目標較小，往 left 走；若目標較大，往 right 走；走到null 還沒找到代表不存在。每一步都排除掉半邊子樹（樹夠平衡的前提下），是 O(h)（h 為樹高，平衡時 h = O(log n)）。- Insert(value)：與 Search 相同的走法找到應該插入的空位（第一個走到 null 的位置），把新節點接在那裡。O(h)。- Delete(value)：先用 Search 找到節點，再依三種情況處理：1. 該節點是葉節點（無子節點）：直接移除。2. 該節點只有一個子節點：用該子節點取代自己的位置（讓父節點直接指向孫節點）。3. 該節點有兩個子節點：不能直接移除（會斷開兩棵子樹），標準做法是找到「中序後繼（in-order successor，即右子樹中最小的節點——一路往右子樹的 left 走到底）」，把後繼節點的值複製到目前節點，再遞迴刪除右子樹中那個後繼節點（後繼節點依定義最多只有右子節點，遞迴刪除時只會落入情況 1 或 2，不會再落入情況 3）。三種情況合計仍是 O(h)。

Complexity 總表：

| 操作 | 平衡樹（h = O(log n)） | 極端退化（h = O(n)） ||---|---|---|| Search | O(log n) | O(n) || Insert | O(log n) | O(n) || Delete | O(log n) | O(n) || 中序走訪拿到排序輸出 | O(n) | O(n) |

Balanced Tree（維持 O(log n) 保證）：BST 的複雜度分析全部建立在「樹高 h = O(log n)」這個假設上，但這個假設不會自動成立——如果插入順序恰好是已排序的資料（例如依序插入1, 2, 3, 4, 5），每個新節點都只會往右子樹走到底，整棵 BST 會退化成一條單向鏈結串列（等同 Day 14 的 Linked List），樹高變成 O(n)，search/insert/delete 全部退化成 O(n)——BST 存在的優勢完全消失。Balanced Tree 就是為了避免這個退化，在 insert/delete 之後主動檢查、修正樹的形狀：- AVL Tree：每個節點額外記錄「左右子樹高度差（balance factor）」，insert/delete 後沿著剛剛異動的路徑往上檢查，一旦某節點的 balance factor 超出 [-1, 1]，透過一次或兩次rotation（把子樹的節點關係做局部重新排列，同時保持 BST「左小右大」不變量不被破壞）把該節點的子樹重新拉平。因為異動路徑長度是 O(log n)（平衡樹的高度），每層最多做一次 O(1) 的 rotation 檢查，整體 insert/delete 維持 O(log n)。- Red-Black Tree：每個節點多一個顏色（紅／黑）欄位，靠一組「紅節點不能有紅子節點」「root 到任一 null 的路徑上黑節點數相同」等規則，保證樹高不超過 2 * log(n+1)——平衡程度比 AVL 略鬆（AVL 更接近完美平衡，查詢略快；Red-Black 允許的重新平衡操作較少，插入/刪除略快），因此 Red-Black Tree 是多數語言標準函式庫（如 Java TreeMap、C++ std::map）的預設選擇，AVL 更常見於「查詢遠多於插入」的場景。

Strength：平衡狀態下 O(log n) 的 search/insert/delete，同時中序走訪還能拿到排序好的完整輸出（Heap 拿不到這個——Day 17 Weakness 提過 Heap 不維護全域排序，這是 BST 相對 Heap 的關鍵優勢，代價是 BST 沒有 Heap 那樣 O(1) 直接拿到 min/max，要沿著一路 left/right 走到底，是 O(log n)）。

Weakness：不維持平衡時可能退化到 O(n)（見上）；維持平衡（AVL/Red-Black）需要額外的欄位（balance factor 或顏色）與 rotation 邏輯，實作複雜度遠高於普通 BST；rotation 本身雖是 O(1)，但頻繁的 insert/delete 觸發的重新平衡仍是額外的常數開銷。

Typical Problems：驗證一棵樹是否為合法 BST、BST 中找第 K 小/大的元素（中序走訪數到第 K 個）、把已排序陣列轉換成高度平衡的 BST、BST 上找最近公共祖先（LCA，可以利用左小右大的性質，比一般 Binary Tree 的 LCA 更快找到）。

Backend Applications：資料庫索引的底層概念與 BST 一脈相承（Phase 04 的 B-Tree 是「每個節點子節點數遠大於 2」的推廣版，解決的正是「磁碟 I/O 昂貴，要讓樹更矮、更胖」的問題）；語言標準函式庫的有序 map/set（Java TreeMap/TreeSet、C++ std::map/std::set）底層是 Red-Black Tree，提供「有序遍歷＋O(log n)查找」的組合能力，是需要「既要快速查找、又要維持排序」時 HashMap 做不到而 BST 系列能做到的場景。

What：Trie（也稱 Prefix Tree）是專門用來儲存與查詢字串集合的樹狀結構：每個節點代表「一個字元」，從 root 到某個節點的路徑組成一個字首（prefix）；每個節點額外有一個 isEndOfWord 標記，代表「從 root 走到這裡剛好組成一個完整儲存過的字串」。

Internal Structure：每個節點包含一組「子節點指標」，依字元集大小決定實作方式——如果字元集固定且小（例如僅小寫英文字母），可以用一個固定大小 26 的 Array（index 對應 字元 - 'a'）；字元集較大或不固定（Unicode、任意字元）則用一個 Map（字元 → 子節點）。這是 Binary Tree「每個節點最多兩個子指標（left/right）」的推廣——Trie 把「最多兩個」放寬成「最多字元集大小個」，子指標從「左/右」變成「依字元索引」。

Core Operations：- Insert(word)：從 root 開始，依序處理 word 每個字元：若目前節點沒有該字元對應的子節點，建立一個新節點；往該子節點移動。處理完最後一個字元後，把該節點標記 isEndOfWord = true。複雜度 O(L)，L 為 word 長度——每個字元只需要一次子節點查找/建立，跟 Trie 裡已經存了多少字串完全無關。- Search(word)：與 Insert 相同的走法，若中途任何字元找不到對應子節點，代表不存在；走完後檢查最後節點的 isEndOfWord是否為 true（否則代表 word 只是別的字串的字首，本身沒被存過）。O(L)。- StartsWith(prefix)：與 Search 相同的走法，但只需要確認路徑存在（不檢查 isEndOfWord），代表存在至少一個字串以prefix 開頭。O(L)，L 為 prefix 長度。

Complexity 總表：

| 操作 | 複雜度 ||---|---|| Insert | O(L)，L 為字串長度 || Search | O(L) || StartsWith（字首查詢） | O(L) |

Strength：搜尋/插入/字首查詢的複雜度只跟字串本身的長度有關，與資料集存了多少個字串無關（BST 的 O(log n) 是隨資料量增加而增加，Trie 的 O(L) 不會）；共用字首的字串天生共用記憶體路徑，字首查詢不需要先取出候選再逐一比對。

Weakness：記憶體開銷可能很大——每個節點若用固定大小 Array（例如 26 個指標）存子節點，即使實際只用到 1、2 個，其餘欄位仍佔用空間，字串集合稀疏（彼此字首重疊少）時浪費明顯（改用 Map 可以省掉沒用到的欄位，但犧牲一點查找常數時間）；只適合以「字首匹配」為核心的查詢，不適合「找出所有包含某個子字串（不一定是字首）的詞」這類需求（那需要其他結構，如後綴樹/陣列，超出本教材範圍）。

Typical Problems：自動完成（autocomplete，見下方綜合練習）、拼字檢查（spell checker，檢查字典裡有沒有這個字，或找出編輯距離最近的候選）、IP 路由表的最長前綴匹配（longest prefix match，概念與字串字首查詢相同，只是把「字元」換成「IP 位址的位元」）、文字接龍/單字搜尋類遊戲盤面上的合法單字判斷。

Backend Applications：自動完成服務用 Trie 存熱門搜尋詞，使用者每打一個字元就沿著 Trie 往下走一層，回傳目前節點以下所有完整字串作為建議；網路路由器用 Trie（或其變體）儲存 IP 前綴與對應的下一跳，靠「最長前綴匹配」決定封包往哪裡送；設定檔/feature flag 系統若 key 有階層命名慣例（例如service.api.timeout），用 Trie 可以支援「列出某個命名空間下所有 key」這類字首查詢。

What：Graph 是由節點（vertex/node）與連接節點的邊（edge）組成的資料結構，是 Tree「拿掉『無環、每個節點只有一個父節點』限制」後的推廣——Tree 是 Graph 的特例（連通、無環），Graph 允許任意節點之間有任意數量的連接，包含環與多個入邊。

Internal Structure（依文件「特別深入」段落逐項展開）：- Directed（有向）：邊有方向性，A → B 不代表 B → A（例如「服務 A 呼叫服務 B」）。- Undirected（無向）：邊沒有方向性，A—B 代表兩個方向都連通（例如「使用者 A 與使用者 B 是朋友」，關係是互相的）。- Weighted（加權）：每條邊額外帶一個權重值，代表「走這條邊的代價」（例如道路的距離、網路連線的延遲）；沒有權重的圖視為每條邊代價相同（unweighted，可視為權重恆為 1）。- Adjacency List：每個節點對應一份「它連到誰」的清單（用 Day 14 的 Linked List 或 Day 11 的 Array 存放），是目前最常見的表示法。- Adjacency Matrix：一個 V × V 的二維陣列（V 為節點數），matrix[i][j] 代表節點 i 到節點 j 是否有邊（或邊的權重）；無向圖的 Matrix 沿對角線對稱。

Core Operations 與複雜度比較（Adjacency List vs Adjacency Matrix，V 為節點數、E 為邊數）：

| 操作 | Adjacency List | Adjacency Matrix ||---|---|---|| 空間 | O(V + E) | O(V²) || 檢查 i,j 是否有邊 | O(degree(i))——需掃過 i 的清單 | O(1)——直接查 matrix[i][j] || 列出節點 i 的所有鄰居 | O(degree(i)) | O(V)——需掃過整列 || 新增一個節點 | O(1) | O(V²)——需重新配置整個矩陣 |

這張表說明兩種表示法是明確的取捨：圖是稀疏的（E 遠小於 V²，多數真實系統的依賴圖/社交圖都是如此）時，Adjacency List 在空間與「列出鄰居」上都遠勝 Matrix；圖是稠密的（E 接近 V²）或需要頻繁「檢查任兩節點是否直接相連」時，Matrix 的 O(1)查找更有優勢。

Complexity（走訪類演算法，以 Adjacency List 為底）：

| 操作 | 複雜度 ||---|---|| BFS / DFS 走訪全部節點與邊 | O(V + E) || 檢查是否有環（見下方陌生題） | O(V + E) |

Strength：能表達任意複雜的關係（環、多對多連接），是 Tree 無法表達的更通用結構；Adjacency List 表示稀疏圖時空間效率高。

Weakness：Adjacency Matrix 在稀疏圖時嚴重浪費空間（多數格子是「無邊」）；圖演算法（最短路徑、環偵測、拓樸排序）普遍比 Tree 的對應演算法複雜，因為節點可能被多條路徑到達，需要額外的 visited 機制避免重複處理或無限迴圈（Day 14 已示範無向圖 BFS/DFS 用 HashSet 記錄 visited）。

Typical Problems：BFS/DFS 走訪（Day 14 已練習過基礎版本）、連通元件（connected components）計數、環偵測（cycle detection，有向圖與無向圖做法不同，見下方陌生題）、拓樸排序（topological sort，只對有向無環圖 DAG 有意義，決定任務執行順序）、最短路徑（Dijkstra 演算法用到 Day 17 的 Heap 取出目前已知距離最短的節點，是 Heap 與 Graph 兩個資料結構的直接組合）。

Backend Applications：微服務之間的呼叫關係、.ai/tasks/*.yaml裡任務的 depends_on 關聯、內部規劃文件¹描述的知識點先後關係，本質上都是有向圖；社交網路的好友/追蹤關係是無向或有向圖；網路拓樸/路由表用加權圖表示，邊權重是延遲或頻寬成本；Build 系統/CI pipeline 的任務依賴（哪個任務要等哪個任務完成）用有向圖表示，並且必須是無環的（有環代表循環依賴，任何一個任務都無法真正開始執行），這正是下方陌生題的情境。