ヒープ | Javascriptを使用したプライオリティキューの実装

導入

ヒープは、ヒープ特性を満たす特別なツリーベースのデータ構造です。
これは完全な二分木です。つまり、左から右に埋められる最後のレベルを除いて、ツリーのすべてのレベルが完全に埋められます。

ヒープには 2 つのタイプがあります:

1. 最大ヒープ
2. 最小ヒープ。

最大ヒープ:

最大ヒープでは、任意のノード I について、I の値はその子の値以上です。
このプロパティは、バイナリ ツリー内のすべてのノードに対して true である必要があります。最も高い値 (最大値) はツリーのルートにあります。

最小ヒープ:

最小ヒープでは、任意のノード I について、I の値はその子の値以下です。
このプロパティは、バイナリ ツリー内のすべてのノードに対して true である必要があります。最も低い値 (最小値) はツリーのルートにあります。

挿入操作と削除操作を実行するたびに、それぞれ bubbleUp と bubbleDown が実行されるため、これらを優先キューと呼ぶことができます。

同じことを配列に実装できますが、leftChildindex、rightChildIndex、parentIndex を計算するにはどうすればよいですか?

式

子供を得るために

2i+1(左)
2i+2 (右)

親を取得するには

i-1/2

以下に minHeap の実装を追加しましたので、ご確認ください。

class MinHeap {
    constructor() {
        this.data = [];
        this.length = 0;
    }

    insert(value) {
        this.data.push(value);
        this.length++;
        this.bubbleUp(this.length-1);
    }

    bubbleUp(index) {

        if (index == 0) {
            return ;
        }

        const parentIndex = this.getParentIndex(index);
        const parentValue = this.data[parentIndex];
        const value = this.data[index];

        if (parentValue > value) {
            this.data[parentIndex] = this.data[index];
            this.data[index] = parentValue;

            this.bubbleUp(parentIndex);
        }
    }

    getParentIndex(index) {
        return Math.floor((index-1)/2);
    }

    getLeftChildIndex(index) {
        return 2*index + 1;
    }

    getRightChildIndex(index) {
        return 2*index + 2;
    }

    bubbleDown(index) {
        if (index >= this.length) {
            return;
        }

        const lIndex = this.getLeftChildIndex(index);
        const rIndex = this.getRightChildIndex(index);

        const lValue = this.data[lIndex];
        const rValue = this.data[rIndex];
        const value = this.data[index];

        if (lValue < rValue && lValue < value) {
            // swap
            this.data[index] = this.data[lIndex];
            this.data[lIndex] = value;
            this.bubbleDown(lIndex);
        } else if (rValue < lValue && rValue < value) {
            this.data[index] = this.data[rIndex];
            this.data[rIndex] = value;
            this.bubbleDown(rIndex)
        }
    }

    delete() {
        if (this.length === 0) {
            return -1;
        }

        const out = this.data[0];
        if (this.length == 1) {
            this.data = [];
            this.length = 0;
            return out;
        }

        this.data[0] = this.data[this.length-1];
        this.length--;
        this.bubbleDown(0);
    }
}

const test = new MinHeap();

test.insert(50);
test.insert(100);
test.insert(101);
test.insert(20);
test.insert(110);
console.log(test)
test.delete();
console.log('---------After Delete -------')
console.log(test)
/*
MinHeap { data: [ 20, 50, 101, 100, 110 ], length: 5 }
---------After Delete -------
MinHeap { data: [ 50, 100, 101, 110, 110 ], length: 4 }
*/

ご質問がございましたら、お気軽にお問い合わせください。

以上がヒープ | Javascriptを使用したプライオリティキューの実装の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。