Heim > Web-Frontend > js-Tutorial > Hauptteil

Haufen | Priority Queue-Implementierung mit Javascript

WBOY
Freigeben: 2024-08-21 12:32:33
Original
621 Leute haben es durchsucht

Heap | Priority Queue Implementation using 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 }
*/

Nach dem Login kopieren

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!

Quelle:dev.to
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!