给定数组A =[10,20,15,12,40,25,18],显示heapify操作后得到的最大堆,并绘制相应的二叉树。
时间: 2024-05-09 18:21:09 浏览: 14
首先,我们需要了解什么是heapify操作。heapify是将一个无序数组转化为堆的过程,堆的特点是父节点比子节点大(最大堆)或者父节点比子节点小(最小堆),堆可以用数组来表示,每个节点的编号为i,那么它的左子节点为2i,右子节点为2i+1,父节点为i/2。
对于给定的数组A,我们可以从最后一个非叶子节点开始进行heapify操作,因为只有非叶子节点才有可能不满足父节点比子节点大的条件。
最后一个非叶子节点的编号为n/2,对于数组A,n=7,所以最后一个非叶子节点的编号为3。
我们从编号为3的节点开始进行heapify操作:
1.比较节点3和它的左右子节点,找出最大值。
2.如果最大值是左子节点,则交换节点3和左子节点的值。
3.重复步骤1和2,直到节点3没有子节点或者它的值已经比左右子节点都大。
4.继续进行heapify操作,对编号为2的节点进行同样的操作。
5.继续进行heapify操作,对编号为1的节点进行同样的操作。
最终得到的最大堆为:[40,20,25,12,10,15,18]
对应的二叉树如下所示:
```
40
/ \
20 25
/ \ / \
12 10 15 18
```
相关问题
Given a max heap H = [40,30,15,10,20], draw the intermediate heaps while conducting the heap sort algorithm.
Intermediate heaps during heap sort algorithm:
Step 1: Remove the root node (40) and replace it with the last node (20). The heap becomes [20,30,15,10,40].
```
40
/ \
30 15
/ \
10 20
20
/ \
30 15
/
10
\
40
```
Step 2: Heapify the heap to maintain the max heap property. The heap becomes [30,20,15,10,40].
```
20
/ \
30 15
/
10
\
40
30
/ \
20 15
/
10
\
40
```
Step 3: Remove the root node (30) and replace it with the last node (10). The heap becomes [10,20,15,30,40].
```
30
/ \
20 15
/
10
\
40
10
/ \
20 15
/
30
\
40
```
Step 4: Heapify the heap to maintain the max heap property. The heap becomes [20,10,15,30,40].
```
10
/ \
20 15
/
30
\
40
20
/ \
10 15
/
30
\
40
```
Step 5: Remove the root node (20) and replace it with the last node (15). The heap becomes [15,10,20,30,40].
```
20
/ \
10 15
/
30
\
40
15
/ \
10 20
/
30
\
40
```
Step 6: Heapify the heap to maintain the max heap property. The heap becomes [10,15,20,30,40].
```
15
/ \
10 20
/
30
\
40
10
/ \
15 20
/
30
\
40
```
Step 7: Remove the root node (10) and replace it with the last node (40). The heap becomes [40,15,20,30].
```
10
/ \
15 20
/
30
\
40
40
/ \
15 20
/
30
```
Step 8: Heapify the heap to maintain the max heap property. The heap becomes [20,15,40,30].
```
15
/ \
40 20
/
30
20
/ \
15 40
/
30
```
Step 9: Remove the root node (20) and replace it with the last node (30). The heap becomes [40,15,30].
```
20
/ \
15 40
/
30
30
/ \
15 40
```
Step 10: Heapify the heap to maintain the max heap property. The heap becomes [40,15,30].
```
30
/ \
15 40
40
/ \
15 30
```
Step 11: Remove the root node (40) and replace it with the last node (30). The heap becomes [30,15].
```
40
/ \
15 30
30
/
15
```
Step 12: Heapify the heap to maintain the max heap property. The heap becomes [30,15].
```
15
/
30
```
Step 13: Remove the root node (30) and replace it with the last node (15). The heap becomes [15].
```
30
/
15
15
```
Step 14: Heapify the heap to maintain the max heap property. The heap becomes [15].
```
15
```
用堆排序完成对数组a中的10个元素从小到大排序。 void main() { int a[10]={18,26,31,72,8,15,88,72,35,20}; int i; heapSort(a,10);
}抱歉,我可以回答您的第一个问题。以下是使用堆排序算法对数组 a 中的 10 个元素进行从小到大排序的代码:
void heapSort(int arr[], int n)
{
// 构造大根堆
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// 一个个把堆顶元素(最大值)放到最后
for (int i = n - 1; i >= 0; i--)
{
// 把堆顶元素与当前未排序部分的最后一个元素交换
swap(arr[0], arr[i]);
// 对交换后的未排序部分重新构造大根堆
heapify(arr, i, 0);
}
}
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)
{
swap(arr[i], arr[largest]);
// 递归地对交换之后的子树进行堆排序
heapify(arr, n, largest);
}
}
int main()
{
int a[10] = {18, 26, 31, 72, 8, 15, 88, 72, 35, 20};
int n = 10;
heapSort(a, n);
// 输出排序结果
for (int i = 0; i < n; i++)
cout << a[i] << " ";
return 0;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)