政大 114 年資管所（科技組） 資料結構 參考答案

1. Build：從 index $\lfloor n/2\rfloor -1$ 往前逐一 heapify-down，建成 Max-Heap。
2. Extract：重複 $n-1$ 次「root 與未排序區最後一個元素交換、heap size 減 1、對新 root 做 heapify-down」，陣列即由小到大排好。

Bottom-up 建 Max-Heap：[214, 162, 138, 95, 82, 36, 14, 78, 56, 31, 12, 6, 9, 2, 7, 3, 22, 10]

反覆將 root 與 heap 末端交換、heap size 減 1、對 root heapify-down（列出取出後剩餘的 heap）：

取出 214：[162, 95, 138, 78, 82, 36, 14, 22, 56, 31, 12, 6, 9, 2, 7, 3, 10]

取出 162：[138, 95, 36, 78, 82, 10, 14, 22, 56, 31, 12, 6, 9, 2, 7, 3]

取出 138：[95, 82, 36, 78, 31, 10, 14, 22, 56, 3, 12, 6, 9, 2, 7]

取出 95：[82, 78, 36, 56, 31, 10, 14, 22, 7, 3, 12, 6, 9, 2]

取出 82：[78, 56, 36, 22, 31, 10, 14, 2, 7, 3, 12, 6, 9]

取出 78：[56, 31, 36, 22, 12, 10, 14, 2, 7, 3, 9, 6]

取出 56：[36, 31, 14, 22, 12, 10, 6, 2, 7, 3, 9]

取出 36：[31, 22, 14, 9, 12, 10, 6, 2, 7, 3]

取出 31：[22, 12, 14, 9, 3, 10, 6, 2, 7]

取出 22：[14, 12, 10, 9, 3, 7, 6, 2]

取出 14：[12, 9, 10, 2, 3, 7, 6]

取出 12：[10, 9, 7, 2, 3, 6]

取出 10：[9, 6, 7, 2, 3]

取出 9：[7, 6, 3, 2]

取出 7：[6, 2, 3]

取出 6：[3, 2]

取出 3：[2]

排序結果：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 78, 82, 95, 138, 162, 214]

1. Partition：範圍 $m~n$，$pk=A[m]$、$i=m+1$、$j=n$。$i$ 右移到第一個 $\ge pk$、$j$ 左移到第一個 $\le pk$，若 $i<j$ 則 swap(A[i],A[j])，重複到 $i,j$ 交會，最後 swap(A[m],A[j])，pivot 歸位。
2. 對左右兩個子區間各自遞迴，直到區間剩 0～1 個元素。

全程只在原陣列內交換，額外空間僅遞迴堆疊。

pivot 取範圍第一個元素，每次 partition 後的陣列：

範圍 0～17，pivot 31 歸位 index 9：[9, 22, 14, 3, 12, 6, 7, 2, 10, 31, 214, 36, 162, 95, 138, 78, 82, 56]

範圍 0～8，pivot 9 歸位 index 4：[6, 2, 7, 3, 9, 12, 14, 22, 10, 31, 214, 36, 162, 95, 138, 78, 82, 56]

範圍 0～3，pivot 6 歸位 index 2：[3, 2, 6, 7, 9, 12, 14, 22, 10, 31, 214, 36, 162, 95, 138, 78, 82, 56]

範圍 0～1，pivot 3 歸位 index 1：[2, 3, 6, 7, 9, 12, 14, 22, 10, 31, 214, 36, 162, 95, 138, 78, 82, 56]

範圍 5～8，pivot 12 歸位 index 6：[2, 3, 6, 7, 9, 10, 12, 22, 14, 31, 214, 36, 162, 95, 138, 78, 82, 56]

範圍 7～8，pivot 22 歸位 index 8：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 214, 36, 162, 95, 138, 78, 82, 56]

範圍 10～17，pivot 214 歸位 index 17：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 56, 36, 162, 95, 138, 78, 82, 214]

範圍 10～16，pivot 56 歸位 index 11：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 162, 95, 138, 78, 82, 214]

範圍 12～16，pivot 162 歸位 index 16：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 82, 95, 138, 78, 162, 214]

範圍 12～15，pivot 82 歸位 index 13：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 78, 82, 138, 95, 162, 214]

範圍 14～15，pivot 138 歸位 index 15：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 78, 82, 95, 138, 162, 214]

排序結果：[2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 78, 82, 95, 138, 162, 214]

1. 建樹：$n$ 個 key 依序插入 AVL tree，每次 $O(\log n)$，共 $O(n\log n)$。
2. 輸出：對樹做 Inorder Traversal，$O(n)$，輸出即遞增序列。

依序插入建 AVL tree，觸發旋轉的插入：

插入 12：節點 14 失衡，LR 旋轉

插入 6：節點 31 失衡，LL 旋轉

插入 7：節點 3 失衡，RR 旋轉

插入 162：節點 82 失衡，RR 旋轉

插入 214：節點 31 失衡，RR 旋轉

插入 9：節點 7 失衡，RL 旋轉

插入 78：節點 82 失衡，LR 旋轉

插入 56：節點 95 失衡，LR 旋轉

其餘插入不需旋轉。最終 AVL tree（層序）：[12, 6, 78, 3, 9, 31, 95, 2, 7, 10, 14, 36, 82, 162, 22, 56, 138, 214]

中序走訪輸出：2, 3, 6, 7, 9, 10, 12, 14, 22, 31, 36, 56, 78, 82, 95, 138, 162, 214

（如簡答圖）