给定序列 (56,38,99,97,66,23,42,12,30,52,6,20),试用筛法建立小顶堆

答案：将序列中的最后一个数字（即20）视为根节点，然后将序列中其余的数字分别与根节点进行比较，若比根节点小，则放入堆，否则丢弃，然后将放入堆中的数字再进行比较，直至构建出小顶堆：12,6,23,20,52,30,42,38,99,97,66。

相关问题

判别以下序列是否为堆，如果不是则将它调整为堆： (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)

对于一个堆，满足以下两个条件：
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)，满足堆的定义。

请将给定数据元素序列84,23,32,54,16,97调整成最大堆。 ‍

好的，让我来为您展示如何将给定的数据元素序列调整成最大堆。

首先，将数据元素序列构建成一个完全二叉树，然后从最后一个非叶子节点（即节点值为32的节点）开始，依次执行以下操作：

1. 比较该节点的值与其左右节点的值，将其与三个节点中的最大值进行交换；
2. 重复上述步骤，直到当前节点是叶子节点或者其子节点的值都小于它的值为止。

按照上述步骤，将数据元素序列84,23,32,54,16,97调整成最大堆后的结果为：97,54,32,84,16,23。

希望这个回答能对您有所帮助，如果您还有其他问题，可以继续问我哦~