【问题描述】用自底向上算法为一组整数构造一个大根堆。 【输入形式】第一行输入一个不为0的整数n,第二行输入需要构造堆的n个整数; 【输出形式】创建好的大根堆; 用C语言解答
时间: 2023-11-30 17:02:50 浏览: 91
对一个含有N整数的数组,使用堆排序让其由小到大输出
好的,下面是使用C语言实现的代码:
```c
#include <stdio.h>
// 自定义swap函数
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 从下向上调整堆
void adjustHeap(int arr[], int i, int n) {
int temp = arr[i];
for (int j = 2 * i; j <= n; j *= 2) {
// 找出左右孩子中较大的一个
if (j < n && arr[j] < arr[j + 1]) {
j++;
}
// 如果父节点比子节点大,跳出循环
if (temp >= arr[j]) {
break;
}
// 将较大的孩子节点赋值给父节点
arr[i] = arr[j];
// 更新i和j的值,继续向下调整
i = j;
}
// 将temp值赋值给最终的i位置
arr[i] = temp;
}
// 构建大根堆
void buildHeap(int arr[], int n) {
// 从最后一个非叶子节点开始,向下调整
for (int i = n/2; i >= 1; i--) {
adjustHeap(arr, i, n);
}
}
int main() {
int n;
scanf("%d", &n);
int arr[n+1];
for (int i = 1; i <= n; i++) {
scanf("%d", &arr[i]);
}
buildHeap(arr, n);
for (int i = 1; i <= n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
```
输入示例:
```
10
2 5 1 8 10 6 3 7 9 4
```
输出示例:
```
10 9 6 8 5 1 3 7 2 4
```
希望能够帮到你!
阅读全文