【问题描述】用自底向上算法为一组整数构造一个大根堆。 【输入形式】第一行输入一个不为0的整数n,第二行输入需要构造堆的n个整数; 【输出形式】创建好的大根堆;
时间: 2023-11-29 08:06:51 浏览: 94
一个关于大整数的算法
好的,下面是代码实现,使用C++语言:
```c++
#include <iostream>
using namespace std;
// 自定义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;
cin >> n;
int arr[n+1];
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
buildHeap(arr, n);
for (int i = 1; i <= n; i++) {
cout << 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
```
希望能够帮到你!
阅读全文