0

数组堆使用 siftdown - max(heap) 这是 45 与 77 交换的结果，我对下一步感兴趣，是 37 与 77 交换还是 45 与 67 交换，考虑到这种情况是由 45 与 77 交换完成的我查看了 1 级（0 级是 37），我是否需要返回以修复 45 和 67 的情况，还是应该继续提高然后修复底部数字？在计算机执行中首先会进行哪些操作？

                            |37|  
            |77|                               |59|  
    |63|             |45|               |54|          |11|
|31|    |39|     |48|    |67|
4

1 回答 1

0

正常的方法在这里：http ://en.wikipedia.org/wiki/Heapsort#Pseudocode 。

从索引 N/2 开始（在图中，容纳 45 的空间。）做一个 siftDOWN。（根据您的描述，您似乎做了一个 siftUP。）如果您从该图开始，您会将 45 与其子项 (48,67) 进行比较并交换 45 和 67。然后从索引中减去一个（item= 63），并在那里进行筛选。继续，直到你到达根。当您与拥有自己子节点的节点进行交换时，您也需要对该节点进行筛选。

如果您按照图中的这个顺序，您可以看到这个模式将检查树中的所有节点。

于 2011-05-12T06:27:43.540 回答