Tas binaires en javascript
La propriété du tas
Cette propriété peut être considérée comme une contrainte pour définir un arbre, une certaine structure qui doit être suivie lors de la construction d'un arbre. Heap définit une relation entre les nœuds parents et ses nœuds enfants, il existe deux types de tas et donc il existe deux types de relations qui peuvent exister entre le nœud parent et le nœud enfant:
- Max-HEAP: La valeur des nœuds parents doit toujours être plus grande ou égale aux nœuds enfants
- Min-heap: la valeur des nœuds parents doit toujours être plus petite ou égale aux nœuds enfants
Une représentation du min-heap est:
(Image de Wikipedia)
Comme vous pouvez le voir, dans l'arbre que les nœuds parents ont des valeurs plus faibles que leurs nœuds enfants
La représentation AR du maximum est:
(Image de Wikipedia)
Vous pouvez voir que les nœuds parents ont des valeurs supérieures à leurs nœuds enfants.
Représentation du tableau
Les tas dans un langage de programmation sont représentés sous la forme d'un tableau, un exemple du réseau de tas construit à partir de l'arborescence maximale ci-dessus est:
var max-heap = [100,19,36,17,3,25,1,2,7];Lorsque vous représentez un tas binaire sous la forme d'un tableau, vous utilisez l'expression suivante pour déduire ce qui suit:
- Enfant gauche = i * 2
- Bon enfant = i * 2 + 1
- Parent = i / 2
Où "je" représente l'index du tableau. En parlant d'index, lorsque nous implémentons des structures de tas à l'aide d'un tableau, nous mettons un "nul" Dans le premier index qui est l'index 0.
Représentation visuelle du travail d'un tas
Pour une représentation virtuelle du fonctionnement d'un min-heap et comment les valeurs sont-elles insérées dans le tas, nous pouvons nous diriger vers le visualiseur de tas de l'Université de San Francisco en cliquant ici
Insérer des valeurs dans le tas, et vous remarquerez comment un nouvel élément est inséré dans le tas en raison de l'animation:
Fonctionnement du tas
Un tas binaire a deux fonctions principales:
- Le premier consiste à ajouter le nouvel élément à sa position appropriée
- La deuxième fonction consiste à supprimer la valeur racinaire
Ajout d'un nouvel élément dans le tas
Un nouvel élément est toujours ajouté à la fin du tableau, puis il est vérifié contre son parent et s'il va à l'encontre de la propriété du tas, il est échangé avec son parent. L'élément est vérifié jusqu'à ce qu'il ait été comparé au nœud racine du tas (le nœud racine est le premier nœud du tas).
Suppression d'un élément du tas
Chaque fois que vous souhaitez supprimer ou récupérer une valeur du tas, vous récupérez toujours la valeur du nœud racine. C'est pourquoi cette valeur est la plus petite valeur si elle est une valeur min et la plus grande valeur si c'est un maximum. Lorsque le nœud racine est retiré du tas, le dernier nœud du tableau prend sa place, il est comparé à ses nœuds enfants pour correspondre à l'état du tas. S'il ne correspond pas à l'état, il est remplacé par son nœud enfant puis vérifié avec d'autres nœuds enfants. Une bien meilleure façon d'expliquer cela consiste à utiliser la visionneuse de tas en direct comme indiqué ci-dessous:
Vous pouvez observer le processus de suppression en observant le GIF ci-dessus.
Implémentation du tas binaire en JavaScript
Nous allons implémenter l'étape par étape de Min-Heap, nous commençons le processus en créant une nouvelle fonction avec les lignes de code suivantes:
Laissez Minheap = fonction ()// Le reste du code Min-Heap sera présent
La première étape consiste à créer un tableau et à définir la valeur à l'index 0 comme nul:
Soit tas = [null];
Alors nous allons créer le insérer une fonction Utilisation des lignes de code suivantes:
ce.insert = fonction (num)
tas.push (num);
si (tas.longueur> 2)
letidx = tas.longueur - 1;
while (tas [idx] = 1)
[tas [mathématiques.plancher (idx / 2)], tas [idx]] = [
tas [idx],
tas [mathématiques.plancher (idx / 2)],
]]
Si (mathématiques.plancher (idx / 2)> 1)
idx = mathématiques.plancher (idx / 2);
autre
casser;
;
Les choses suivantes se produisent dans cet extrait de code:
- Un nouvel élément nobs est ajouté au dernier indice du tableau
- Si la longueur du tableau est supérieure à 2 éléments, nous vérifions le nouvel élément avec son nœud parent
- Si l'élément est plus petit que son nœud parent, il est remplacé par son nœud parent, sinon nous déduisons que le tas dans le bon ordre
- Si l'élément est remplacé par son nœud parent à l'étape précédente, nous le comparons à nouveau avec son nouveau parent jusqu'à ce que nous déduisons que le tas est dans un ordre correct ou que l'élément devient le nœud racine
L'étape suivante consiste à implémenter le supprimer la fonction avec les lignes de code suivantes:
ce.supprimer = fonction ()Soit le plus petit = tas [1];
si (tas.longueur> 2)
tas [1] = tas [tas.longueur - 1];
tas.épisser (tas.longueur - 1);
si (tas.longueur == 3)
if (tas [1]> tas [2])
[tas [1], tas [2]] = [tas [2], tas [1]];
retourner le plus petit;
leti = 1;
LETLEFT = 2 * I;
LetRight = 2 * i + 1;
while (tas [i]> = tas [gauche] || tas [i]> = tas [à droite])
if (tas [gauche] < heap[right])
[tas [i], tas [gauche]] = [tas [gauche], tas [i]];
i = 2 * i;
autre
[tas [i], tas [à droite]] = [tas [à droite], tas [i]];
i = 2 * i + 1;
gauche = 2 * i;
à droite = 2 * i + 1;
if (tas [gauche] == Undefined || tas [à droite] == Undefined)
casser;
elseif (tas.longueur == 2)
tas.épissure (1, 1);
autre
retourner null;
retourner le plus petit;
;
Les étapes suivantes se produisent dans l'extrait de code ci-dessus:
- Nous supprimons le nœud racine car c'est le plus petit nœud du tas
- Si le tas n'a que deux éléments, alors le 2ème élément devient le nœud racine
- Si le tas a 3 éléments, le plus petit des 2e et 3e élément devient le nœud racine
- Si l'élément a plus de 3 éléments, alors le dernier élément du tas devient le nœud racine
- Ensuite, ce nouveau nœud racine est comparé à ses nœuds enfants et est remplacé par le nœud plus petit et est contre les nouveaux nœuds enfants (pour le remplacement, nous utilisons le Méthode de destructeur d'objets)
- Ce processus de comparaison de l'élément avec les nœuds enfants est répété jusqu'à ce qu'il atteigne un point où il est plus petit que les deux nœuds enfants ou qu'il devient le dernier nœud du tableau.
L'étape suivante consiste à créer une fonction qui nous affichera le tableau de tas de la console, nous le faisons en utilisant les lignes de code suivantes:
ce.show = function ()console.journal (tas);
;
L'extrait de code complet de la mise en œuvre de la structure de données Min-Heap est:
letminheap = function ()Soit tas = [null];
ce.insert = fonction (num)
tas.push (num);
si (tas.longueur> 2)
letidx = tas.longueur - 1;
while (tas [idx] = 1)
[tas [mathématiques.plancher (idx / 2)], tas [idx]] = [
tas [idx],
tas [mathématiques.plancher (idx / 2)],
]]
Si (mathématiques.plancher (idx / 2)> 1)
idx = mathématiques.plancher (idx / 2);
autre
casser;
;
ce.supprimer = fonction ()
Soit le plus petit = tas [1];
si (tas.longueur> 2)
tas [1] = tas [tas.longueur - 1];
tas.épisser (tas.longueur - 1);
si (tas.longueur == 3)
if (tas [1]> tas [2])
[tas [1], tas [2]] = [tas [2], tas [1]];
retourner le plus petit;
leti = 1;
Laisse gauche = 2 * i;
Laisse à droite = 2 * i + 1;
while (tas [i]> = tas [gauche] || tas [i]> = tas [à droite])
if (tas [gauche] < heap[right])
[tas [i], tas [gauche]] = [tas [gauche], tas [i]];
i = 2 * i;
autre
[tas [i], tas [à droite]] = [tas [à droite], tas [i]];
i = 2 * i + 1;
gauche = 2 * i;
à droite = 2 * i + 1;
if (tas [gauche] == Undefined || tas [à droite] == Undefined)
casser;
elseif (tas.longueur == 2)
tas.épissure (1, 1);
autre
returnnull;
retourner le plus petit;
;
ce.show = function ()
console.journal (tas);
;
;
Ce que nous devons faire maintenant, c'est de créer un nouveau min-heap en utilisant la fonction Minheap que nous venons de créer, puis d'y ajouter des éléments en utilisant l'insert et afficher le tas. Pour ce faire, nous fabriquons une nouvelle variable et la cartographier sur le Minheap en utilisant les lignes de code suivantes:
var NewMinheap = new Minheap ();Ensuite, ajoutons des valeurs au tas en utilisant les lignes de code suivantes:
Newminheap.insérer (34);Newminheap.insérer (61);
Newminheap.insérer (138);
Newminheap.insérer (82);
Newminheap.insérer (27);
Newminheap.insérer (35);
Maintenant, nous appelons le montrer Fonction Pour afficher le réseau de tas sur la console:
Newminheap.montrer();Nous obtenons le résultat suivant sur notre console:
Comme vous pouvez le voir, le premier élément du tableau est nul. Les autres nœuds ne sont pas plus gros que leurs nœuds enfants. Par exemple, si nous prenons le nœud avec la valeur 35. L'enfant à gauche et à droite est comme:
Vous pouvez clairement voir, le le parent (35) est plus petit que son enfant gauche (82) et son enfant droit (61). De même, chaque nœud parent est plus petit que son nœud enfant, nous pouvons donc déduire que notre code fonctionne parfaitement
De même, en modifiant simplement la condition de comparaison pour que le nœud parent soit plus petit que l'enfant au nœud parent étant plus grand que le nœud enfant, nous pouvons implémenter le Maximum Utilisation des lignes de code suivantes:
letMaxHeap = function ()Soit tas = [null];
ce.insert = fonction (num)
tas.push (num);
si (tas.longueur> 2)
letidx = tas.longueur - 1;
tandis que (tas [idx]> tas [mathématiques.plancher (idx / 2)])
if (idx> = 1)
[tas [mathématiques.plancher (idx / 2)], tas [idx]] = [
tas [idx],
tas [mathématiques.plancher (idx / 2)],
]]
Si (mathématiques.plancher (idx / 2)> 1)
idx = mathématiques.plancher (idx / 2);
autre
casser;
;
ce.supprimer = fonction ()
Soit le plus petit = tas [1];
si (tas.longueur> 2)
tas [1] = tas [tas.longueur - 1];
tas.épisser (tas.longueur - 1);
si (tas.longueur == 3)
if (tas [1] < heap[2])
[tas [1], tas [2]] = [tas [2], tas [1]];
retourner le plus petit;
leti = 1;
Laisse gauche = 2 * i;
Laisse à droite = 2 * i + 1;
Pendant (tas [i] <= heap[left] || heap[i] heap[right])
[tas [i], tas [gauche]] = [tas [gauche], tas [i]];
i = 2 * i;
autre
[tas [i], tas [à droite]] = [tas [à droite], tas [i]];
i = 2 * i + 1;
gauche = 2 * i;
à droite = 2 * i + 1;
if (tas [gauche] == Undefined || tas [à droite] == Undefined)
casser;
elseif (tas.longueur == 2)
tas.épissure (1, 1);
autre
returnnull;
retourner le plus petit;
;
ce.show = function ()
console.journal (tas);
;
;
C'est tout, vous avez mis en œuvre avec succès un tas binaire en JavaScript
Conclusion
Les tas binaires sont la mise en œuvre pariétale d'un arbre binaire ayant la condition d'avoir au plus Deux nœuds enfants pour chaque nœud parent et la structure complète de l'arbre binaire. Ce qui signifie que les niveaux de l'arbre seront remplis à partir du côté gauche ou de l'enfant gauche, puis de la droite.
Les tas binaires font partie des structures de données avancées, et il existe deux types d'arbre binaire: l'un d'eux est appelé le tas min tandis que l'autre est appelé le tas max. Dans le Min-Heap, les nœuds parents ont des valeurs plus petites que leurs nœuds enfants et les valeurs des nœuds de frère.
De même, dans Max-Heap, les valeurs du nœud parent sont toujours supérieures à leur nœud enfant et les valeurs des nœuds de frère. Dans cet article, nous avons appris sur les tas et leur implémentation dans Vanilla JavaScript et à la fin, nous avons testé notre implémentation.