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。 parent 的计算公式为

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

Q3。以及计算左右的公式children 而不是：

    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，你可能会说它不是它自己的父级，但公式就是这样计算的。

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

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

while循环停止条件缺失

While loop stop condition missing

java

algorithm

heap

data-structures