111 年 國立政治大學資訊管理學系碩士班科技組《資料結構》

a) Min‑Heap 建構
以 1 為基底陣列索引，依底層至根部自下而上 siftdown：

最終的最小堆（1‑index）
$[1,\;7,\;3,\;19,\;16,\;5,\;12,\;28,\;35,\;92,\;48,\;17,\;22,\;18]$

對應二元樹：

          1
      /       \
     7         3
   /   \     /   \
 19   16   5     12
/ \   / \  / \   / \
28 35 92 48 17 22 18

b) Min‑Heap 排序演算法

1. 建堆：$O(n)$ 的 heapify。
2. 重複以下 $n$ 次
   • 輸出根節點（最小值）。
   • 將最後一個節點移到根，堆大小 $n-1$。
   • 在根位置 siftdown，維持最小堆性質（$O(\log n)$）。

整體時間 $O(n\log n)$，空間 $O(1)$（原地）或 $O(n)$（額外輸出陣列）。

c) 應用於本題

a) AVL 樹構造

插入順序依次調整旋轉後得到的平衡樹如下（每個節點後括號內為平衡因子）：

          17(0)
         /      \
      5(0)      28(-1)
     /   \     /      \
  3(+1) 12(0) 18(0)   48(0)
  /      / \        /     \
1(+1)  7(0) 16(0) 35(+1) 92(0)
               /
             22(0)

b) AVL 排序演算法

1. 依次將所有鍵 key 插入空 AVL 樹 T（每次插入後執行必要的單/雙旋轉，保證 O(log n)）。
2. 完成插入後，以 中序走訪（左子樹 → 根 → 右子樹）遍歷 T，將走訪到的鍵依序輸出，即為遞增序列。

偽代碼：

核心觀念

本題考查 Merge Sort（合併排序） 的分治法：

1. Divide：將序列反覆分成左右兩半，直到每個子序列只剩一個元素。
2. Conquer：單一元素的序列視為已排序。
3. Merge：將兩個已排序的子序列，依序合併成一個較大的已排序序列。

合併時，比較左右兩個子序列目前最前面的元素，將較小者放入結果序列，直到其中一邊耗盡，再接上另一邊剩餘元素。

若資料筆數為 $n$，遞迴式為

$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$

因此時間複雜度為

$$T(n)=O(n\log n)$$

Merge Sort 通常需要 $O(n)$ 的額外空間；若左右元素相等時優先取左邊元素，則可維持排序的穩定性。

---

解題方法

原始序列為

$$17,\ 35,\ 12,\ 28,\ 16,\ 5,\ 18,\ 7,\ 19,\ 92,\ 48,\ 3,\ 22,\ 1$$

先採用由上而下的分治法切割，再由下而上合併。

---

分割階段

第一次分割

$$\begin{aligned} &[17,35,12,28,16,5,18]\\ &[7,19,92,48,3,22,1] \end{aligned}$$

第二次分割

左半部：

$$[17,35,12]\qquad [28,16,5,18]$$

右半部：

$$[7,19,92]\qquad [48,3,22,1]$$

繼續分割至單一元素

左側：

$$[17,35,12]\rightarrow [17]\quad [35,12]$$ $$[35,12]\rightarrow [35]\quad [12]$$ $$[28,16,5,18]\rightarrow [28,16]\quad [5,18]$$ $$[28,16]\rightarrow [28]\quad [16]$$ $$[5,18]\rightarrow [5]\quad [18]$$

右側：

$$[7,19,92]\rightarrow [7]\quad [19,92]$$ $$[19,92]\rightarrow [19]\quad [92]$$ $$[48,3,22,1]\rightarrow [48,3]\quad [22,1]$$ $$[48,3]\rightarrow [48]\quad [3]$$ $$[22,1]\rightarrow [22]\quad [1]$$

---

合併階段

1. 合併最小子序列

合併 $[35]$ 與 $[12]$

比較 $35$ 與 $12$：

$$[35]+[12]\rightarrow [12,35]$$

合併 $[17]$ 與 $[12,35]$

比較過程：

• $17<12$ 不成立，取 $12$
• 比較 $17$ 與 $35$，取 $17$
• 剩下 $35$

因此：

$$[17]+[12,35]\rightarrow [12,17,35]$$

---

合併 $[28]$ 與 $[16]$

$$[28]+[16]\rightarrow [16,28]$$

合併 $[5]$ 與 $[18]$

$$[5]+[18]\rightarrow [5,18]$$

合併 $[16,28]$ 與 $[5,18]$

比較過程：

• 取 $5$
• 取 $16$
• 取 $18$
• 剩下 $28$

因此：

$$[16,28]+[5,18]\rightarrow [5,16,18,28]$$

---

2. 合併左半部

合併

$$[12,17,35]\quad\text{與}\quad[5,16,18,28]$$

逐步比較：

核心觀念

本題考查：

• Quick-Sort 的分割（partition）程序。
• 以子陣列的第一個元素作為 pivot。
• In-place 操作：直接在原陣列中交換元素，不另建立左右兩個陣列。
• 分割完成後，pivot 左側元素皆小於 pivot，右側元素皆大於 pivot，再遞迴處理左右子陣列。

採用雙指標分割法。設左指標 $i$、右指標 $j$：

1. $j$ 從右向左尋找小於 pivot 的元素。
2. $i$ 從左向右尋找大於 pivot 的元素。
3. 交換這兩個元素。
4. 當 $i>j$ 時，將 pivot 與 $A[j]$ 交換，使 pivot 歸位。

Quick-Sort 平均時間複雜度為 $O(n\log n)$，最差為 $O(n^2)$；此題採用 in-place 分割，因此額外空間主要來自遞迴堆疊，平均為 $O(\log n)$。

---

解題方法

原始陣列為：

$$[17,35,12,28,16,5,18,7,19,92,48,3,22,1]$$

以下每次皆選取目前子陣列的第一個元素作為 pivot。

---

第一層分割：pivot = 17

初始：

$$[17,35,12,28,16,5,18,7,19,92,48,3,22,1]$$

左指標從 $35$ 開始，右指標從 $1$ 開始。

• $j$ 找到 $1<17$，$i$ 找到 $35>17$，交換：

$$[17,1,12,28,16,5,18,7,19,92,48,3,22,35]$$

• $j$ 往左找到 $3<17$，$i$ 往右找到 $28>17$，交換：

$$[17,1,12,3,16,5,18,7,19,92,48,28,22,35]$$

• $j$ 往左找到 $7<17$，$i$ 往右找到 $18>17$，交換：

$$[17,1,12,3,16,5,7,18,19,92,48,28,22,35]$$

此時指標交錯，將 pivot $17$ 與 $7$ 交換：

$$[7,1,12,3,16,5,17,18,19,92,48,28,22,35]$$

因此 $17$ 歸位，陣列分成：

$$[7,1,12,3,16,5]\quad 17\quad [18,19,92,48,28,22,35]$$

---

處理左子陣列：$[7,1,12,3,16,5]$

此段 pivot 為 $7$。

• $j$ 找到 $5<7$，$i$ 找到 $12>7$，交換：

$$[7,1,5,3,16,12]$$

• 指標交錯，將 $7$ 與 $3$ 交換：

$$[3,1,5,7,16,12]$$

因此：

$$[3,1,5]\quad 7\quad [16,12]$$

---

處理子陣列：$[3,1,5]$

pivot 為 $3$。

• $i$ 找到 $5>3$，$j$ 從右側往左找到 $1<3$。
• 指標交錯，將 $3$ 與 $1$ 交換：

$$[1,3,5]$$

因此 $3$ 歸位：

$$[1]\quad 3\quad [5]$$