申論題

四、假設有個陣列 A[1..n]儲存著 n 個整數。可將 A[1..n]看成二元樹，其中 A[1] 是樹根。A[i]的左右子節點分別為 A[2i]和 A[2i + 1], i =1, 2, . . . , n/2。若 2i＞n 或 2i+1＞n，則這些子節點是不存在的。若 A 滿足 A[i] ≥ max{A[2i], A[2i + 1]},1 ≤ i ≤ n/2，則稱陣列 A[1..n]是一個堆疊（heap）。假設有個副 程式 sift(A, r, n)其輸入參數 A 是一個陣列，n 是 A 的大小，r ≤ n 是一個 指標，指向此子樹的樹根。副程式 sift(A, r, n)的功能是將 A[r]為樹根的 子樹變成 heap。在呼叫 sift(A, r, n)之前，它的左右子樹都已經是 heap。 副程式 sift(A, r, n)所需的計算時間是 O(h(r))，其中 h(r)是以 A[r]為樹根 的子樹的高度，也就是從樹根到任一樹葉的最長距離。 （每小題 10 分，共 20 分）

⑵分析以上所設計演算法的計算複雜度為 O(n)。