阿摩線上測驗
6.下列何者最能代表 Heap 的性質？
(A)每個節點的左右子樹 高度相同
(B)完全二元樹 + 父節點大於(或小於)子節點
(C)所有節點按數值大小排序
(D)任意二元樹即可稱為 Heap
統計： A(0), B(11), C(6), D(1), E(0) #3678237
詳解 (共 1 筆)
【解題思路】
抓關鍵字：「Heap 的性質」「完全二元樹」「父節點大小關係」。
Heap（堆積）最重要的兩大特性：
-
形狀性質（shape property）：必須是「完全二元樹（complete binary tree）」
→ 不能缺洞、不能亂長 -
堆積性質（heap property）：父節點必須 ≥（Max-Heap）或 ≤（Min-Heap） 子節點
→ 但兄弟節點彼此沒有順序要求
→ 整棵樹也不是排序過的樹（不是 BST）
只有 (B) 完全符合。
【逐一破題：為什麼其他選項不正確】
(A) 左右子樹高度相同
→ 那是 AVL Tree（高度平衡樹）的特性，不是 Heap。
Heap 只要求「完全二元樹」，不要求左右高度相同。
(C) 所有節點按數值大小排序
→ 這是 Binary Search Tree（BST）的特性，不是 Heap。
Heap 不保證排序，只保證父節點 ≥ 或 ≤ 子節點。
(D) 任意二元樹即可稱為 Heap
→ 錯。Heap 必須是「完全二元樹」，任意形狀不行。
【延伸知識】
Heap 常用於：
-
優先佇列 Priority Queue（最常見應用）
-
Heap Sort（排序演算法）
Heap 的兩種型態：
-
Max-Heap：父節點 ≥ 子節點
-
Min-Heap：父節點 ≤ 子節點
注意：
Heap 不是完全排序結構！
例如 Max-Heap 的 root 是最大值，但左右子樹並非一定排序。
【記憶技巧】
口訣：
「Heap 兩件事：形狀要完整，爸比要最大（或最小）。」
或：
「完全二元樹＋父子有序＝Heap。」
【常見錯誤】
-
把 Heap 當成 BST，以為整棵樹排序 → 錯
-
以為 Heap 必須平衡 → 錯
-
以為任意二元樹都能當 Heap → 錯
-
把 Max-Heap 與 Min-Heap 混淆 → 父節點大於或小於子節點就對了
總結（圖示比較）
| 選項 | 樹的樣子 | 是否符合 Heap？ | 原因 |
|---|---|---|---|
| (A) | AVL（平衡樹） | ✗ | 不是完全二元樹規定，也沒有父子大小限制 |
| (B) | 完全二元樹 + 父節點 ≥ 子節點 | ✔ | Max/Min Heap 的標準定義 |
| (C) | 二元搜尋樹 BST | ✗ | 左 < 根 < 右，不是 Heap 規則 |
| (D) | 任意形狀的二元樹 | ✗ | 不符合 Heap 的形狀與大小性質 |
【BST 的核心規則（一定要記）】
在二元搜尋樹（Binary Search Tree, BST）裡：
-
左子樹的值 < 父節點的值
-
右子樹的值 > 父節點的值
-
每個節點都遵守這條規則（遞迴性質）
要看父子關係，就是從「父節點」往下看它左邊和右邊的節點。
一層層看（非常重要）
第一層：根（Root）
-
15 是根（因為它沒有父節點）
它的子節點：
-
左子：7（因為 7 < 15）
-
右子：20（因為 20 > 15）
【BST 不會怎麼樣？（避免誤解）】
這些都不是 BST 的父子規則：
× 父節點不一定最大／最小（那是 Heap）
× 子節點之間不必排序（兄弟沒有排序關係）
× 整棵樹不必長得很美（只要遵守大小規則即可）
【把三種樹一起比較（最重要的表格）】
| 名稱 | 重點規則 | 是否要求樹形狀？ | 是否要求每節點子數？ | 是否要求左對齊？ |
|---|---|---|---|---|
| 有根樹 Rooted Tree | 只要有根即可 | 不要求 | 不要求 | 不要求 |
| 完整樹 Full Tree | 每個節點必須是 0 子或 2 子 | 要求 | 要求 | 不要求 |
| 完全樹 Complete Tree | 節點從左到右填滿，最後一層靠左 | 要求 | 不要求 | 要求 |
一句話記：
-
有根樹：只要有根就行，最寬鬆。
-
完整樹：每個節點只能是 0 或 2 子。
-
完全樹：形狀最整齊，長得像 Heap。
【為什麼我們需要知道 Full、Complete、Rooted Tree？】
因為：「樹的形狀」會影響「資料結構的效率」。
也就是說：
不同的樹形 → 不同的演算法效率 → 不同的應用場景
就像建築物：
-
有些建築是階梯型（適合看台）
-
有些建築是方形（適合住人）
-
有些建築是高塔型（適合觀測）
樹狀結構也是一樣。
【1. 有根樹（Rooted Tree）：定義起點】
意義：
只要你有一個「根」，整棵樹就有方向、有層次、有父子關係。
為什麼重要？
因為幾乎所有資料結構都是有根的，包括：
-
Binary Tree（二元樹）
-
Binary Search Tree（BST）
-
Heap
-
Trie
-
Segment Tree
-
AVL Tree
-
Red-Black Tree
如果沒有「根」，你無法定義：
-
父子關係
-
遞迴遍歷方式（前序、中序、後序）
-
搜尋方向
所以 Rooted Tree 就是「所有樹結構的基礎」。
你需要知道它，因為：
只要有樹的題目，就一定需要父子定義，而這就是 Rooted Tree。
【2. 完整樹（Full Tree）：控制節點的子數】
意義：
Full Tree 定義了「每個節點只能有 0 或 2 個子節點」。
這個結構常用來：
-
表示某些樹的數學性質
-
幫助判斷樹是否偏斜
-
用於特定演算法分析
雖然 Full Tree 比較少直接用來實作資料結構，但它有助於理解：
為什麼有些樹會比較「平衡」？為什麼搜尋效率好或差？
尤其在 BST 分析時，會用 Full Tree 的特性去推導節點數量、深度等數學關係。
【3. 完全樹（Complete Tree）：Heap 的形狀 → 直接影響效率】
最重要的是「完全樹 Complete Tree」。
意義：
Heap（優先佇列 Priority Queue）的形狀一定是「完全樹」。
為什麼？
因為：
-
插入快
-
刪除快
-
用陣列存更快（不需要指標）
-
沒有多餘空洞（記憶體高效使用）
只有完全樹，才能保證：
-
Heap 中最大（或最小）值在 root
-
插入 O(log n)
-
刪除 O(log n)
-
用 array 存就能找到父子位置
也就是說：
完全樹是 Heap 高效率的秘密。
你需要知道它，因為：
-
Heap Sort
-
Priority Queue
-
Dijkstra 最短路徑（用最小 Heap）
-
A* 搜尋
-
Event Scheduling
-
CPU 排程
-
即時系統任務處理
全都用到 Heap，而 Heap 一定是「完全樹」。
【一句話總結每種樹的意義】
| 樹種類 | 你為什麼需要它？ | 它的主要用途 |
|---|---|---|
| 有根樹 Rooted Tree | 所有樹結構的起點。沒有它就沒有父子關係。 | 所有樹、遍歷、遞迴定義 |
| 完整樹 Full Tree | 用來理解「樹的數學性質」與「節點平衡」。 | 推導樹的高度、節點數 |
| 完全樹 Complete Tree | Heap 的基礎，影響「插入/刪除效率」。 | Priority Queue、Heap Sort |
【直接告訴你：為什麼考這些？】
因為考試希望你能：
-
用樹的形狀推斷演算法效率（O(log n) or O(n)）
-
區分 BST、Heap、AVL 是怎樣靠樹形來提高效率
-
知道記憶體如何用 array 儲存樹（Complete Tree 才能做）
-
了解演算法為什麼設計成這樣（不是隨便找個形狀）
如果你搞懂這三種樹，你會：
馬上理解 Heap、BST、AVL、Trie 為什麼長成那樣。
