java - while循环停止条件缺失

Question

在此geeksforgeeks min heap 实现，看起来像 insert 方法 while 循环边界条件缺少检查。

如果我错了，请纠正我？

public void insert(int element) {
    if (size >= maxsize) {
        return;
    }
    Heap[++size] = element;
    int current = size;

    while (Heap[current] < Heap[parent(current)]) {
        swap(current, parent(current));
        current = parent(current);
    }
}


private void swap(int fpos, int spos) {
    int tmp;
    tmp = Heap[fpos];
    Heap[fpos] = Heap[spos];
    Heap[spos] = tmp;
}

private int parent(int pos) {
    return pos / 2;
}

Q1。 while 循环不应该是:

while (current != 0 && Heap[current] < Heap[parent(current)])

代替

while (Heap[current] < Heap[parent(current)])

Q2。父级计算公式

private int parent(int pos) {
        return (pos - 1) / 2;
    }

Q3。以及计算左右 child 的公式而不是:

    private int leftChild(int pos) 
    { 
        return (2 * pos); 
    } 

    private int rightChild(int pos) 
    { 
        return (2 * pos) + 1; 
    } 

应该是

    private int leftChild(int pos) 
    { 
        return (2 * pos) + 1; 
    } 

    private int rightChild(int pos) 
    { 
        return (2 * pos) + 2; 
    } 

Answer 1

0 的 parent 也是 0，您可能会争辩说它实际上不是它自己的父级，但这就是公式的计算结果。

堆的根不能小于它自己，所以循环自动停在那里。

父公式和左/右子公式大致有两个版本:一个版本适用于索引为 1 的数组(根的索引为 1)，另一种版本适用于索引为 0 的数组(根有索引 0)。在 0 索引版本中，子索引是通过将 0 或 1 位附加到父索引(在最低有效位)形成的，父索引是通过删除最低有效位从子索引中找到的。 1 索引版本必须补偿额外的偏移量。