0

这里我们有一个二进制堆的数组实现的片段。我想要一些帮助来了解这个 for 循环在伪代码中的含义：

public void insert (Anytype x) { 
    int hole = ++currentSize; //currentSize is the size of the array
    for (array[0] = x; x.compareTO(array[hole / 2]) < 0; hole /= 2)
        array[hole] = array[hole / 2];
    array[hole] = x;
}

我似乎无法理解这个 for 循环是如何工作的。谢谢你。

编辑填补了这个漏洞

4

2 回答 2

1

转换成二叉堆的数组可以看成如下

         [elem 0] <-- put the inserted element here? (why? a precaution perhaps?)

         [element 1]...
    [element2] [ element3 ]  
[elem4][elem5] [elem6][elem7]  
[x][x] [x][x]  [x][XX] ... <-- unoccupied

代码通过将索引孔除以 2 到达每个节点的父节点。然后，如果父节点 > 当前节点，它将父节点向上移动到当前节点。

我认为有一个错误......至少这不是典型的解决方案，将插入的元素作为最后一个未被占用的“洞”并从那个位置向上移动......

正确的方法是开始比较最后一个元素的父元素并迭代到根元素。没有必要交换，但是索引“洞”结束的地方，那是最终放置新元素的合适位置。（典型的解决方案将 'X' 放在最后一个位置并交换，但这是低效的。） for 循环中的第一次初始化也是不必要的。

无论如何，当索引 0 被省略时，索引算术是有效的。

于 2012-10-25T07:10:08.307 回答
0

我不太确定你在找什么，但这里有：

compareTo 返回一个整数。如果 x 小于 y，x.compareTo(y) 返回一个负数。

所以代码大致是这样的：

for( set the first pos in the array to x; if x is less than array[hole/2]; hole/=2){
   array[hole] = array[hole/2];

Set your arr[final val of hole] to x
于 2012-10-25T07:10:38.760 回答