用堆排序对序列“18,40,30,80,21,70,52,32,15,90”进行初始堆化
时间: 2024-04-14 18:31:42 浏览: 28
好的,我来为你进行堆排序的初始堆化。
首先,我们将序列转换成一个最大堆。最大堆是一种满足父节点大于等于其子节点的特性的二叉树。
初始序列:
[18, 40, 30, 80, 21, 70, 52, 32, 15, 90]
我们从最后一个非叶子节点开始,依次向上进行操作。
第一步:最后一个非叶子节点是父节点52,它的左子节点是70,右子节点是32。我们比较父节点和两个子节点的大小,将最大的值交换到父节点的位置。
交换后的序列:
[18, 40, 30, 80, 21, [70], [52], 32, 15, 90]
第二步:继续向前,处理父节点40。它的左子节点是80,右子节点是21。我们比较父节点和两个子节点的大小,将最大的值交换到父节点的位置。
交换后的序列:
[18, [80], 30, [40], 21, 70, 52, 32, 15, 90]
第三步:继续向前,处理父节点18。它的左子节点是80,右子节点是30。我们比较父节点和两个子节点的大小,将最大的值交换到父节点的位置。
交换后的序列:
[[80], 18, [30], 40, 21, 70, 52, 32, 15, 90]
现在,我们完成了一次初始堆化操作。最大堆的性质被满足。
最终的初始堆化结果为:
[80, 18, 30, 40, 21, 70, 52, 32, 15, 90]
希望这个示例能够帮助你理解堆排序的初始堆化过程。如果还有其他问题,请随时提问!
相关问题
一组关键字序列为(50,40,95,20,15,70,60,45,80),采用堆排序方法进行递增排序,建立初始最大值堆
这里是一组关键字序列为(50,40,95,20,15,70,60,45,80)建立初始最大值堆的过程:
1. 首先将整个序列看作一个完全二叉树,根据完全二叉树的性质,从最后一个非叶子节点开始,对每个非叶子节点进行调整,以满足最大堆的性质。
初始状态的完全二叉树如下:
50
/ \
40 95
/ \ / \
20 15 70 60
/ \
45 80
最后一个非叶子节点是节点 2,因此从节点 2 开始进行调整。
2. 对于每个非叶子节点,首先比较其左右子节点的大小,选取较大的子节点与该节点进行比较。如果该节点比其子节点小,则将该节点与较大的子节点交换,并继续向下比较。如果该节点比其子节点大,则调整结束。
对节点 2 进行调整,比较其与左右子节点的大小,发现左子节点的值为 40,右子节点的值为 95,因此将节点 2 与右子节点交换,得到以下结果:
50
/ \
95 40
/ \ / \
20 15 70 60
/ \
45 80
继续对节点 2 进行调整,比较其与左右子节点的大小,发现左子节点的值为 20,右子节点的值为 15,因此将节点 2 与左子节点交换,得到以下结果:
50
/ \
95 80
/ \ / \
20 15 70 60
/ \
45 40
继续对节点 1 进行调整,比较其与左右子节点的大小,发现左子节点的值为 95,右子节点的值为 80,因此将节点 1 与左子节点交换,得到以下结果:
95
/ \
50 80
/ \ / \
20 15 70 60
/ \
45 40
继续对节点 0 进行调整,比较其与左右子节点的大小,发现左子节点的值为 50,右子节点的值为 80,因此将节点 0 与右子节点交换,得到以下结果:
95
/ \
80 50
/ \ / \
20 15 70 60
/ \
45 40
继续对节点 0 进行调整,比较其与左右子节点的大小,发现左子节点的值为 80,右子节点的值为 50,因此将节点 0 与左子节点交换,得到以下结果:
80
/ \
95 50
/ \ / \
20 15 70 60
/ \
45 40
继续对节点 0 进行调整,比较其与左右子节点的大小,发现左子节点的值为 95,右子节点的值为 50,因此将节点 0 与左子节点交换,得到以下结果:
95
/ \
80 50
/ \ / \
20 15 70 60
/ \
45 40
3. 当所有非叶子节点都被调整完成后,整个序列就变成了一个最大堆。此时,将堆顶元素(即序列中的最大值)与序列的最后一个元素交换位置,并将序列的长度减 1。
将 95 与 80 交换位置,得到以下结果:
80
/ \
50 95
/ \ / \
20 15 70 60
/ \
45 40
将序列长度减 1,得到以下序列:
80, 50, 70, 45, 15, 40, 60, 95
4. 重复步骤 1~3,直到序列长度为 1,排序完成。
对于这个序列,重复以上步骤,最终得到以下排序结果:
15, 40, 45, 50, 60, 70, 80, 95
因此,这个序列的递增排序结果为(15, 40, 45, 50, 60, 70, 80, 95)。
堆排序之从无序序列创建初始堆
堆排序是一种常见的排序算法,其中一个重要的步骤就是从无序序列创建初始堆。这个过程也被称为堆化(heapify)。
具体的实现步骤如下:
1. 从最后一个非叶子节点开始,依次向上遍历整棵树。最后一个非叶子节点的位置为 n/2-1,其中n为序列的长度。
2. 对于当前遍历到的节点,如果它的值小于左子节点或右子节点的值,那么将当前节点的值与左右子节点中最大的一个进行交换。
3. 继续向上遍历,直到根节点。
4. 这样就完成了从无序序列创建初始堆的过程。
需要注意的是,在这个过程中,我们并不需要真正地构建一棵树,只是逻辑上将序列看成一棵完全二叉树进行操作。同时,这个过程的时间复杂度为 O(n),其中 n 为序列的长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)