对下面序列进行堆排序: (05,56,20,23,40,38,29,61,35,76,28,100)要求: (1)给出创建大顶堆的结果; (2)给出交换第三大数字并重新调整后堆的结果。
时间: 2023-09-12 10:10:13 浏览: 60
1. 创建大顶堆的过程:
首先将序列构建为一个完全二叉树:
```
05
/ \
56 20
/ \ / \
23 40 38 29
/ \ / \ / \
61 35 76 28 100
```
从最后一个非叶子节点开始,即从23开始,依次向上进行调整:
1. 将23与其子树中的最大值交换,得到以下树:
```
05
/ \
56 76
/ \ / \
28 40 38 29
/ \ / \ / \
61 35 23 20 100
```
2. 将56与其子树中的最大值交换,得到以下树:
```
76
/ \
56 38
/ \ / \
28 40 23 29
/ \ / \ / \
61 35 05 20 100
```
3. 将76与其子树中的最大值交换,得到以下树:
```
76
/ \
61 38
/ \ / \
28 40 23 29
/ \ / \ / \
05 35 56 20 100
```
4. 将76与其子树中的最大值交换,得到以下树:
```
100
/ \
61 76
/ \ / \
28 40 23 29
/ \ / \ / \
05 35 56 20 38
```
5. 将61与其子树中的最大值交换,得到以下树:
```
100
/ \
56 76
/ \ / \
28 40 23 29
/ \ / \ / \
05 35 61 20 38
```
6. 将56与其子树中的最大值交换,得到以下树:
```
100
/ \
38 76
/ \ / \
28 40 23 29
/ \ / \ / \
05 35 61 20 56
```
7. 将38与其子树中的最大值交换,得到以下树:
```
100
/ \
35 76
/ \ / \
28 40 23 29
/ \ / \ / \
05 38 61 20 56
```
8. 将35与其子树中的最大值交换,得到以下树:
```
100
/ \
29 76
/ \ / \
28 40 23 35
/ \ / \ / \
05 38 61 20 56
```
9. 将29与其子树中的最大值交换,得到以下树:
```
100
/ \
28 76
/ \ / \
05 40 23 35
/ \ / \ / \
29 38 61 20 56
```
此时我们已经得到了一个大顶堆。
2. 交换第三大数字并重新调整后堆的结果:
首先将第三大数字23与最后一个数字100交换,得到以下序列:
(05,56,20,100,40,38,29,61,35,76,28,23)
然后对序列重新进行堆排序,得到以下序列:
(05,56,20,100,40,38,29,61,35,76,28,23)
将序列构建为一个完全二叉树:
```
05
/ \
56 20
/ \ / \
100 40 38 29
/ \ / \ / \
61 35 76 28 23
```
从最后一个非叶子节点开始,即从56开始,依次向上进行调整:
1. 将56与其子树中的最大值交换,得到以下树:
```
05
/ \
100 20
/ \ / \
56 40 38 29
/ \ / \ / \
61 35 76 28 23
```
2. 将100与其子树中的最大值交换,得到以下树:
```
100
/ \
61 20
/ \ / \
56 40 38 29
/ \ / \ / \
05 35 76 28 23
```
3. 将100与其子树中的最大值交换,得到以下树:
```
100
/ \
61 76
/ \ / \
56 40 38 29
/ \ / \ / \
05 35 20 28 23
```
4. 将100与其子树中的最大值交换,得到以下树:
```
76
/ \
61 35
/ \ / \
56 40 38 29
/ \ / \ / \
05 20 100 28 23
```
5. 将76与其子树中的最大值交换,得到以下树:
```
61
/ \
56 35
/ \ / \
05 40 38 29
/ \ / \ / \
76 20 100 28 23
```
6. 将61与其子树中的最大值交换,得到以下树:
```
56
/ \
05 35
/ \ / \
76 40 38 29
/ \ / \ / \
61 20 100 28 23
```
7. 将56与其子树中的最大值交换,得到以下树:
```
76
/ \
05 35
/ \ / \
61 40 38 29
/ \ / \ / \
56 20 100 28 23
```
8. 将76与其子树中的最大值交换,得到以下树:
```
61
/ \
05 35
/ \ / \
56 40 38 29
/ \ / \ / \
76 20 100 28 23
```
此时我们已经得到了调整后的序列。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)