嘿,我试着用javascript实现一个最小堆,但是我有一个关于remove m in算法的问题,我使用一个数组在内部表示堆当我向下渗透时,停止的条件应该是什么?在我的代码中,它的大小是2*k

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;
};

最佳答案

我想如果条件允许的话你会错过的当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;
    }

关于javascript - javascript中的最小堆,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/35978242/

10-11 23:00
查看更多