【PTA数据结构 | C语言版】二叉堆的快速建堆操作

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，将 n 个顺序存储的数据用快速建堆操作调整为最小堆；最后顺次输出堆中元素以检验操作的正确性。

输入格式：
输入首先给出一个正整数 c（≤1000），为最小堆的最大容量；下一行给出正整数 n（≤c）；随后一行给出 n 个元素。所有元素均为 int 型范围内的整数。

输出格式：
在 n 行中按层序遍历的顺序每行输出一个最小堆元素。

输入样例：
10
6
7 3 9 5 2 8

输出样例：
2
3
8
5
7
9

代码

#include <stdio.h>
#include <stdlib.h>void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;
}// 向下调整堆，维护最小堆性质
void siftDown(int arr[], int n, int i) {int smallest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && arr[left] < arr[smallest])smallest = left;if (right < n && arr[right] < arr[smallest])smallest = right;if (smallest != i) {swap(&arr[i], &arr[smallest]);siftDown(arr, n, smallest);}
}// 快速建堆：Floyd算法，自底向上调整非叶子节点
void buildHeap(int arr[], int n) {for (int i = n / 2 - 1; i >= 0; i--)siftDown(arr, n, i);
}int main() {int c, n;scanf("%d", &c);scanf("%d", &n);int *arr = (int *)malloc(c * sizeof(int));for (int i = 0; i < n; i++)scanf("%d", &arr[i]);buildHeap(arr, n);// 按层序遍历输出（数组顺序即为层序）for (int i = 0; i < n; i++)printf("%d\n", arr[i]);return 0;
}