113 年 國立中正大學電機工程學系碩士班計算機工程組《資料結構》

題目只寫 heap，未指定最大堆或最小堆；以下採最大堆（max-heap）定義作答。

核心觀念

最大堆必須同時滿足：

1. 結構上是完整二元樹。
2. 每個節點的值都不小於其子節點：

$$A[\text{parent}] \ge A[\text{child}]$$

使用從 $0$ 開始的陣列索引時：

$$\text{left}(i)=2i+1,\qquad \text{right}(i)=2i+2$$

陣列中的葉節點不需要調整。最後一個非葉節點的索引為：

$$\left\lfloor \frac{n}{2}\right\rfloor-1$$

因此可採用「由下而上建立堆積」（bottom-up heap construction），從最後一個非葉節點一路處理到根節點。

i. 原地建立最大堆的函式

void siftDownMax(int a[], int n, int i)
{
    while (2 * i + 1 < n) {       // 至少有左子節點
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int larger = left;

        // 找出兩個子節點中較大的節點
        if (right < n && a[right] > a[left])
            larger = right;

        // 父節點已不小於較大的子節點，調整完成
        if (a[i] >= a[larger])
            break;

        // 交換父節點與較大的子節點
        int temp = a[i];
        a[i] = a[larger];
        a[larger] = temp;

        // 繼續檢查交換後往下移動的節點
        i = larger;
    }
}

void buildMaxHeap(int a[], int n)
{
    for (int i = n / 2 - 1; i >= 0; --i)
        siftDownMax(a, n, i);
}

此方法沒有使用額外陣列，只使用一個暫存變數 temp 進行交換，因此符合題目要求。

建立順序由下而上是必要的：處理節點 $i$ 時，其左右子樹已經先被整理成最大堆，siftDownMax 只需將節點 $i$ 向下移動，直到恢復最大堆性質。

ii. 處理指定陣列

初始陣列為：

$$[10,\ 3,\ 40,\ 5,\ 100]$$

其完整二元樹為：

        10
       /  \
      3    40
     / \
    5  100

陣列長度 $n=5$，最後一個非葉節點為：

$$\left\lfloor\frac{5}{2}\right\rfloor-1=1$$

因此依序處理索引 $1$、索引 $0$。

核心觀念

題目中的「method above」未附出；以下採用標準的「自底向上建構 Max-Heap」方法，並將其整合到 Heap Sort 中。

本題考查：

• Max-Heap 的性質
• Bottom-Up Heap Construction
• Heapify／下濾操作
• In-place sorting
• Heap Sort 的時間複雜度分析

對於以 $0$ 為起始索引的陣列：

$$\text{left}(i)=2i+1,\qquad \text{right}(i)=2i+2$$

Max-Heap 必須滿足：

$$A[\text{parent}(i)]\ge A[i]$$

因此根節點 $A[0]$ 永遠是目前堆積中的最大值。若要將資料排序成遞增，應使用 Max-Heap，依序把最大值放到陣列最右側。

---

解題方法

排序流程如下：

1. 將整個陣列建構成 Max-Heap。
2. 將根節點最大值與目前堆積的最後一個元素交換。
3. 將堆積大小縮小一格，已放到右側的最大值不再參與堆積。
4. 對新的根節點執行 Max-Heapify，恢復 Max-Heap 性質。
5. 重複上述步驟，直到堆積只剩一個元素。

其中，葉節點本身已經是合法的 Heap，因此只需從最後一個非葉節點開始，反向處理至根節點。

---

關鍵程式碼

以下採用迭代式 maxHeapify，不使用遞迴，因此除了給定陣列外，不需要額外的陣列或遞迴堆疊。

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

/* 將 A[i] 下濾，使 A[0...heapSize-1] 維持 Max-Heap */
void maxHeapify(int A[], int heapSize, int i)
{
    while (1)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < heapSize && A[left] > A[largest])
            largest = left;

        if (right < heapSize && A[right] > A[largest])
            largest = right;

        if (largest == i)
            break;

        swap(&A[i], &A[largest]);
        i = largest;
    }
}

/* 自底向上建構 Max-Heap */
void buildMaxHeap(int A[], int n)
{
    int i;

    for (i = n / 2 - 1; i >= 0; i--)
        maxHeapify(A, n, i);
}

/* Heap Sort：將 A[0...n-1] 排成遞增順序 */
void heapSort(int A[], int n)
{
    int heapSize;

    buildMaxHeap(A, n);

    for (heapSize = n; heapSize > 1; heapSize--)
    {
        /* A[0] 是目前最大值，放到目前堆積的最後 */
        swap(&A[0], &A[heapSize - 1]);

        /* A[heapSize-1] 已排序，只處理前 heapSize-1 個元素 */
        maxHeapify(A, heapSize - 1, 0);
    }
}

例如，當目前 heapSize = 6 時：

• 堆積範圍為 A[0] 到 A[5]
• A[0] 是這 6 個元素中的最大值
• 交換後，A[5] 確定為目前應放置的最大值
• 下一次只對 A[0] 到 A[4] 重新建堆

---

正確性說明

建堆完成後，陣列的前 n 個元素符合 Max-Heap 性質，因此：

$$A[0]=\max(A[0],A[1],\ldots,A[n-1])$$

每次迭代維持以下不變量：

核心觀念

本題考加權圖的鄰接矩陣表示法，以及用 Dijkstra 演算法求單一起點到所有其他節點的最短路徑。

圖中邊的權重皆為正數，且圖為無向圖，因此鄰接矩陣對稱。Dijkstra 每次選出目前距離起點最近、尚未確定的節點，再用它更新相鄰節點的距離。

i. 鄰接矩陣

依照原圖，邊為 $AB=9$、$AF=3$、$BC=1$、$BF=5$、$CD=3$、$CE=2$、$DE=6$、$EF=1$。矩陣中以 $\infty$ 表示沒有直接連線。

節點順序採 $A,B,C,D,E,F$：

$$\begin{array}{c|rrrrrr} & A & B & C & D & E & F\\ \hline A & 0 & 9 & \infty & \infty & \infty & 3\\ B & 9 & 0 & 1 & \infty & \infty & 5\\ C & \infty & 1 & 0 & 3 & 2 & \infty\\ D & \infty & \infty & 3 & 0 & 6 & \infty\\ E & \infty & \infty & 2 & 6 & 0 & 1\\ F & 3 & 5 & \infty & \infty & 1 & 0 \end{array}$$

無向圖滿足 $w(i,j)=w(j,i)$，所以矩陣沿主對角線對稱；沒有邊的位置設為 $\infty$，對角線設為 $0$。

ii. A 到各節點的最短路徑

依序更新距離：

1. 從 $A$ 出發：$d(F)=3$、$d(B)=9$。
2. 經過 $F$：$d(E)=3+1=4$，$d(B)=\min(9,3+5)=8$。
3. 經過 $E$：$d(C)=4+2=6$，$d(D)=4+6=10$。
4. 經過 $C$：$d(B)=\min(8,6+1)=7$，$d(D)=\min(10,6+3)=9$。

因此五條最短路徑如下：

目的地	最短路徑	路徑成本
$B$	$A \to F \to E \to C \to B$	$3+1+2+1=7$
$C$	$A \to F \to E \to C$	$3+1+2=6$
$D$	$A \to F \to E \to C \to D$	$3+1+2+3=9$
$E$	$A \to F \to E$	$3+1=4$
$F$	$A \to F$	$3$

iii. Dijkstra 演算法

令 dist[v] 儲存起點到節點 v 的目前最短距離；visited[v] 表示該距離是否已確定。每輪從尚未確定的節點中選出 dist 最小者，再檢查矩陣中的所有節點並嘗試鬆弛距離。