java - 解释这个 for 循环片段

Question

这里我们有一个二进制堆的数组实现的片段。我需要一些帮助来了解这个 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 循环是如何工作的。谢谢。

编辑填补了这个漏洞

Answer 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 被省略时，索引算术才有效。