设初始无序序列(36,48,48,90,88,80,76,99),求使用堆排序的方法建立的初始大顶堆,请画出该大顶堆。
时间: 2024-05-26 09:06:19 浏览: 71
Java 堆排序实例(大顶堆、小顶堆)
5星 · 资源好评率100%
以下是使用堆排序方法建立的初始大顶堆的示例:
初始无序序列:(36,48,48,90,88,80,76,99)
大顶堆的建立过程如下:
1. 从最后一个非叶子节点开始,向上调整每个子树,使其满足大顶堆的性质。
- 最后一个非叶子节点的索引为 n/2-1,其中 n 是序列的长度。
- 对于初始无序序列,最后一个非叶子节点的索引为 3。
2. 从最后一个非叶子节点开始,依次向上调整每个子树,使其满足大顶堆的性质。
- 每次调整的过程是将当前节点与其左右子节点中的较大值进行比较,如果当前节点小于较大值,则交换两者的位置。
- 调整完成后,继续向上调整父节点,直到根节点。
下面是大顶堆的建立过程:
```
初始无序序列:(36,48,48,90,88,80,76,99)
第一次调整:
36
/ \
48 48
/ \ / \
90 88 80 76
/
99
第二次调整:
36
/ \
48 99
/ \ / \
90 88 80 76
/
48
第三次调整:
99
/ \
48 90
/ \ / \
36 88 80 76
/
48
第四次调整:
99
/ \
88 90
/ \ / \
36 48 80 76
/
48
大顶堆建立完成。
```
阅读全文