用C语言编程将序列:7,4,9,15,2,6,10建成堆并输出。
时间: 2024-06-16 22:07:47 浏览: 25
在 C 语言中,可以使用数组来表示堆。堆有两种形式:大根堆和小根堆。对于大根堆,父节点的值大于等于子节点的值;对于小根堆,父节点的值小于等于子节点的值。本题要求将序列 7, 4, 9, 15, 2, 6, 10 建成大根堆并输出,可以按照以下步骤实现:
1. 将序列转化为完全二叉树,从最后一个非叶子节点开始进行堆化操作。
2. 堆化操作包括:比较当前节点与其左右子节点的大小,若当前节点小于其左右子节点中较大的一个,则交换当前节点与其左右子节点中较大的一个;然后对交换后的子节点递归进行堆化操作。
3. 重复步骤2直到整个二叉树成为大根堆。
按照上述步骤,建成的大根堆为:15, 7, 10, 4, 2, 6, 9。以下是 C 语言代码实现:
```
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void buildHeap(int arr[], int n) {
int i;
for (i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
int main() {
int arr[] = {7, 4, 9, 15, 2, 6, 10};
int n = sizeof(arr) / sizeof(arr);
buildHeap(arr, n);
printf("大根堆:");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)