0

こんにちは、javascript で最小ヒープを実装しようとしましたが、最小値を削除するためのアルゴリズムについて質問がありました。内部でヒープを表すために配列を使用しています。下に浸透している場合、停止条件はどうすればよいですか? 私のコードでは、 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条件が1つ欠けていると思います。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 に答える