本專欄持續輸出數據結構題目集，歡迎訂閱。

題目

請編寫程序，將 n 個已經滿足 d 叉最小堆順序約束的數據直接讀入最小堆；隨后將下一個讀入的數據 x 插入堆；再執行刪頂操作并輸出刪頂的元素；最后順次輸出堆中剩余元素以檢驗操作的正確性。

輸入格式：
輸入在第 1 行給出 2 個正整數 c（2<c≤1000）和 d（1<d≤4），依次對應最小堆的最大容量和樹的度；下一行給出正整數 n（<c）；隨后一行按層序遍歷的順序給出 n 個最小堆元素；最后一行給出將要插入堆的元素 x。所有堆元素均為 int 型范圍內的整數。

輸出格式：
在一行中輸出插入后再刪頂的元素，格式為 min = y，其中 y 為刪頂元素值。
隨后 n 行，按層序遍歷的順序每行輸出一個最小堆元素。

輸入樣例：
10 3
9
1 3 4 6 7 10 8 5 9
2

輸出樣例：
min = 1
2
3
4
6
7
10
8
5
9

代碼

#include <stdio.h>
#include <stdlib.h>void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 向上調整，維護d叉最小堆性質
void siftUp(int arr[], int n, int d, int i) {while (i > 0) {int parent = (i - 1) / d;if (arr[i] >= arr[parent]) break;swap(&arr[i], &arr[parent]);i = parent;}
}// 向下調整，維護d叉最小堆性質
void siftDown(int arr[], int n, int d, int i) {while (1) {int smallest = i;int startChild = d * i + 1;int endChild = startChild + d;for (int j = startChild; j < endChild && j < n; j++) {if (arr[j] < arr[smallest]) {smallest = j;}}if (smallest == i) break;swap(&arr[i], &arr[smallest]);i = smallest;}
}int main() {int c, d, n;scanf("%d %d", &c, &d);scanf("%d", &n);int *heap = (int *)malloc(c * sizeof(int));if (heap == NULL) {fprintf(stderr, "內存分配失敗\n");return 1;}for (int i = 0; i < n; i++) {scanf("%d", &heap[i]);}int x;scanf("%d", &x);// 插入新元素heap[n] = x;siftUp(heap, n + 1, d, n);n++;// 刪頂操作int min = heap[0];heap[0] = heap[n - 1];n--;siftDown(heap, n, d, 0);// 輸出結果printf("min = %d\n", min);for (int i = 0; i < n; i++) {printf("%d\n", heap[i]);}return 0;
}