0

嘿，我尝试在 javascript 中实现最小堆，但我对删除 min 的算法有疑问。我在内部使用一个数组来表示堆。当我向下渗透时，停止条件应该是什么？在我的代码中，我将其设置为 2 * k <= this.size，因此它可能会向下移动到最后一个元素，但感觉不“正确”，是否有更好的停止条件？提前致谢！

this.removeMin = function () {
    //replace root with last element and percolate downwards
    var min = this._heap[1],
        k,
        left,
        right;

    this._heap[1] = this._heap.pop();
    this.size--;
    k = 1;

    while ( ( 2 * k ) <= this.size) {
        left = 2 * k;
        right = 2 * k + 1;

        if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
            if (this._heap[left] <= this._heap[right]) {
                swap(this._heap, k, left);
                k = left;
            } else {
                swap(this._heap, k, right);
                k = right;
            }
        } else if (this._heap[k] > this._heap[left]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    }

    return min;
};
4

2 回答 2

1

我认为你错过了一个 if 条件。当第k个元素都小于右边和左边时，向下必须停止。肯定是：

   if (this._heap[k] > this._heap[left] && this._heap[k] > this._heap[right]) {
        if (this._heap[left] <= this._heap[right]) {
            swap(this._heap, k, left);
            k = left;
        } else {
            swap(this._heap, k, right);
            k = right;
        }
    } else if (this._heap[k] > this._heap[left]) {
        swap(this._heap, k, left);
        k = left;
    } else if(this._heap[k] < this._heap[right]) {
        swap(this._heap, k, right);
        k = right;
    }else{
        break;
    }
于 2016-03-14T02:22:08.557 回答
0

为什么你一次又一次地编写比较代码。共享以下代码以供参考，这将优化您的代码，您可以将其替换为您的 while 循环。

.....
while (2 * k <= this.size) {
        let j = 2 * key;
        if (j < this.size && less(j, j + 1)) j++; // find smallest child
        if (!less(k, j)) break; // check parent is lesser than smallest child or not
        exch(k, j); //if parent is bigger then exchange
        k = j; //keep checking untill reaches to the end(this.size)
    }
.....
function less(i, j){
    if(this._heap[j] < this._heap[i] < 0) return true;
    else return false;
}
function exch(i, j){
    let temp = this._heap[i];
    this._heap[i] = this._heap[j];
    this._heap[j] = temp;
}

希望这有效。

于 2020-06-06T17:30:26.970 回答