Tas | Implémentation de file d'attente prioritaire à l'aide de Javascript

Introduction

Un tas est une structure de données arborescente spéciale qui satisfait à la propriété tas.
Il s'agit d'un arbre binaire complet, ce qui signifie que tous les niveaux de l'arbre sont entièrement remplis à l'exception du dernier niveau, qui est rempli de gauche à droite.

Il existe deux types de tas :

1. tas maximum
2. min tas.

Tas maximum :

Dans un tas max, pour tout nœud I donné, la valeur de I est supérieure ou égale aux valeurs de ses enfants.
Cette propriété doit être vraie pour tous les nœuds de l'arborescence binaire. La valeur la plus élevée (maximale) se trouve à la racine de l'arbre.

Tas minimum :

Dans un tas min, pour tout nœud I donné, la valeur de I est inférieure ou égale aux valeurs de ses enfants.
Cette propriété doit être vraie pour tous les nœuds de l'arborescence binaire. La valeur la plus basse (minimum) se trouve à la racine de l'arbre.

Nous pouvons les appeler une file d'attente prioritaire car chaque fois que nous effectuons une opération d'insertion et de suppression, cela fera respectivement bubbleUp et bubbleDown.

On peut implémenter la même chose dans un tableau mais comment calculer les leftChildindex, rightChildIndex et parentIndex ?

Formule

Pour avoir un enfant

2i+1(gauche)
2i+2 (à droite)

Pour obtenir un parent

i-1/2

Ci-dessous, j'ai ajouté une implémentation de minHeap, veuillez vérifier.

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

Faites-moi savoir si vous avez des questions, n'hésitez pas à vous connecter.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!