PAT 甲級 05-樹6：最小堆路徑查詢（插入建堆 + 父節點回溯）

題目大意

• 給定 N 個整數，依次插入初始為空的最小堆
• 隨後給定 M 個下標（1-based），對每個下標 i，輸出從 H[i] 到根節點的路徑
• 路徑格式：數值空格分隔，行末無多餘空格

數據結構：最小堆（數組實現）

typedef struct {
    int *elements;  // 1-based 索引，[0] 為哨兵
    int size;
    int capacity;
} MinHeap;

核心操作

1. 建堆/插入 Insert

void Insert(MinHeap H, int item) {
    int i = ++H->size;
    for (; H->elements[i/2] > item; i /= 2)
        H->elements[i] = H->elements[i/2];  // 上浮
    H->elements[i] = item;
}

哨兵 elements[0] = -10001 保證比所有可能值小，簡化邊界判斷。

2. 路徑打印 Print

void Print(MinHeap H, int *idx, int M) {
    for (int k = 0; k < M; k++) {
        int i = idx[k];
        if (i > H->size) continue;  // 防越界（題目保證合法可省略）
        while (i > 0) {
            printf("%d", H->elements[i]);
            if (i > 1) printf(" ");
            else printf("\n");
            i /= 2;  // 移至父節點
        }
    }
}

完整主流程

int main() {
    int N, M; scanf("%d%d", &N, &M);
    MinHeap H = Create(N);
    for (int i=0, x; i<N; i++) { scanf("%d",&x); Insert(H,x); }
    int idx[M]; for (int i=0; i<M; i++) scanf("%d",&idx[i]);
    Print(H, idx, M);
    return 0;
}

樣例驗證

Input:
5 3
46 23 26 24 10
5 4 3

堆結構（層序）：[10, 23, 26, 46, 24]
下標 5 → 24 23 10
下標 4 → 46 23 10
下標 3 → 26 10

複雜度

• 建堆：O(N log N)
• 單次查詢：O(log N)（路徑長度）
• 空間：O(N)