判别以下序列是否为堆,如果不是则将它调整为堆: (1) (100,86,48,73,35,39,42,57,66,21) (2) (12,70,33,65,24,56,48,92,86,33) (3) (103,97,56,38,66,23,42,12,30,52,6,20) (4) (5,6,20,30,40,35,42,76,28)
时间: 2023-09-17 14:12:02 浏览: 281
对于一个堆,满足以下两个条件:
1. 它是一棵完全二叉树。
2. 对于任意一个非叶子节点,其值不小于(或不大于)其子节点的值。
根据上述定义,对于给定的序列,我们可以判断其是否为堆,并进行调整操作。
(1) (100,86,48,73,35,39,42,57,66,21)
这个序列不是堆,因为它不满足第二个条件,例如节点 1 的值 100 大于其子节点 2 的值 86。
调整方法如下:
1. 从最后一个非叶子节点开始,向前遍历所有非叶子节点。
2. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
3. 重复步骤2,直到根节点。此时序列变成了 (100,86,48,73,66,39,42,57,35,21),满足堆的定义。
(2) (12,70,33,65,24,56,48,92,86,33)
这个序列不是堆,因为它不满足第二个条件,例如节点 2 的值 70 大于其子节点 5 的值 56。
调整方法如下:
1. 从最后一个非叶子节点开始,向前遍历所有非叶子节点。
2. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
3. 重复步骤2,直到根节点。此时序列变成了 (92,70,48,65,24,56,33,12,86,33),满足堆的定义。
(3) (103,97,56,38,66,23,42,12,30,52,6,20)
这个序列不是堆,因为它不满足第二个条件,例如节点 2 的值 97 大于其子节点 5 的值 23。
调整方法如下:
1. 从最后一个非叶子节点开始,向前遍历所有非叶子节点。
2. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
3. 重复步骤2,直到根节点。此时序列变成了 (103,97,56,38,66,23,42,12,30,52,6,20),不满足堆的定义。
4. 从倒数第二层开始,向上遍历所有非叶子节点。
5. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
6. 重复步骤5,直到根节点。此时序列变成了 (103,97,56,38,66,52,42,12,30,23,6,20),满足堆的定义。
(4) (5,6,20,30,40,35,42,76,28)
这个序列不是堆,因为它不满足第二个条件,例如节点 1 的值 6 小于其子节点 3 的值 30。
调整方法如下:
1. 从最后一个非叶子节点开始,向前遍历所有非叶子节点。
2. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
3. 重复步骤2,直到根节点。此时序列变成了 (76,30,42,5,40,35,20,6,28),不满足堆的定义。
4. 从倒数第二层开始,向上遍历所有非叶子节点。
5. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
6. 重复步骤5,直到根节点。此时序列变成了 (76,40,42,5,30,35,20,6,28),不满足堆的定义。
7. 从第二个节点开始,向上遍历所有非叶子节点。
8. 对于每个非叶子节点,比较其值和其子节点的值,并将其与较大(或较小)的子节点交换位置。
9. 重复步骤8,直到根节点。此时序列变成了 (76,40,42,6,30,35,20,5,28),满足堆的定义。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)