对下面序列进行堆排序: (05,56,20,23,40,38,29,61,35,76,28,100)要求: (1)给出创建大顶堆的结果; (2)给出交换第三大数字并重新调整后堆的结果。
时间: 2023-09-23 16:11:21 浏览: 65
堆排序是一种基于堆的排序算法,它的基本思想是将待排序序列构造成一个大顶堆或者小顶堆,然后依次取出堆顶元素,得到一个有序序列。
对于该序列,堆排序的过程如下:
1. 创建大顶堆,从最后一个非叶子节点开始向前遍历,对每个节点进行堆调整,使得以该节点为根节点的子树成为大顶堆。
初始序列:(05,56,20,23,40,38,29,61,35,76,28,100)
第一步:从最后一个非叶子节点开始进行堆调整,将以该节点为根节点的子树调整为大顶堆。
05
/ \
56 20
/ \ / \
61 35 76 28
/ \ / \ / \
23 40 38 29 100
第二步:继续向前遍历,对每个节点进行堆调整。
05
/ \
56 38
/ \ / \
61 35 76 28
/ \ / \ / \
23 40 20 29 100
05
/ \
76 38
/ \ / \
61 35 56 28
/ \ / \ / \
23 40 20 29 100
76
/ \
61 56
/ \ / \
23 35 38 28
/ \ / \ / \
05 40 20 29 100
最终得到大顶堆:(76,61,56,38,28,35,23,05,40,29,20,100)
2. 交换第三大数字并重新调整堆。
将第三大数字 56 与堆顶元素 76 进行交换,得到序列 (56,61,20,23,40,38,29,05,35,76,28,100)。
对于新的序列,将第一个元素 56 与其左右子节点 61 和 20 进行比较,发现 61 更大,因此交换 56 和 61,得到序列 (61,56,20,23,40,38,29,05,35,76,28,100)。
接着将第一个元素 61 与其左右子节点 56 和 20 进行比较,发现 61 更大,不需要交换。
继续将第一个元素 61 与其左右子节点 23 和 40 进行比较,发现 61 更大,不需要交换。
将第一个元素 61 与其左右子节点 38 和 29 进行比较,发现 61 更大,不需要交换。
将第一个元素 61 与其左右子节点 05 和 35 进行比较,发现 61 更大,不需要交换。
将第一个元素 61 与其左右子节点 76 和 28 进行比较,发现 76 更大,交换 61 和 76,得到序列 (76,56,20,23,40,38,29,05,35,61,28,100)。
继续将第一个元素 76 与其左右子节点 56 和 20 进行比较,发现 76 更大,不需要交换。
将第一个元素 76 与其左右子节点 23 和 40 进行比较,发现 76 更大,不需要交换。
将第一个元素 76 与其左右子节点 38 和 29 进行比较,发现 76 更大,不需要交换。
将第一个元素 76 与其左右子节点 05 和 35 进行比较,发现 76 更大,不需要交换。
将第一个元素 76 与其左右子节点 61 和 28 进行比较,发现 76 更大,不需要交换。
最终得到新的大顶堆:(76,56,38,23,40,35,29,05,61,28,20,100)。
相关推荐
![](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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)