Haufen | Priority Queue-Implementierung mit Javascript

Einführung

Ein Heap ist eine spezielle baumbasierte Datenstruktur, die die Heap-Eigenschaft erfüllt.
Es handelt sich um einen vollständigen Binärbaum, was bedeutet, dass alle Ebenen des Baums vollständig gefüllt sind, mit Ausnahme der letzten Ebene, die von links nach rechts gefüllt wird.

Es gibt zwei Arten von Heaps:

1. maximaler Heap
2. min. Heap.

Max. Heap:

In einem Max-Heap ist für jeden gegebenen Knoten I der Wert von I größer oder gleich den Werten seiner untergeordneten Knoten.
Diese Eigenschaft muss für alle Knoten im Binärbaum wahr sein. Der höchste Wert (Maximum) liegt an der Wurzel des Baumes.

Min. Heap:

In einem Min-Heap ist für jeden gegebenen Knoten I der Wert von I kleiner oder gleich den Werten seiner untergeordneten Knoten.
Diese Eigenschaft muss für alle Knoten im Binärbaum wahr sein. Der niedrigste Wert (Minimum) liegt an der Wurzel des Baums.

Wir können sie als Prioritätswarteschlange bezeichnen, da jedes Mal, wenn wir einen Einfüge- und Löschvorgang ausführen, ein BubbleUp bzw. BubbleDown erfolgt.

Wir können dasselbe in einem Array implementieren, aber wie berechnet man leftChildindex, rightChildIndex und parentIndex?

Formel

Ein Kind bekommen

2i+1(links)
2i+2 (rechts)

Um Eltern zu werden

i-1/2

Unten habe ich eine Implementierung von minHeap hinzugefügt, bitte überprüfen Sie.

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 }
*/

Lassen Sie mich wissen, wenn Sie Fragen haben. Nehmen Sie einfach Kontakt auf.

Das obige ist der detaillierte Inhalt vonHaufen | Priority Queue-Implementierung mit Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!