这里我们有一个二进制堆的数组实现的片段。我需要一些帮助来了解这个 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 循环是如何工作的。谢谢。
编辑填补了这个漏洞
最佳答案
数组转换成二叉堆可以看到如下
[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 被省略时，索引算术才有效。
关于java - 解释这个 for 循环片段，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13063216/