Montones binarios en JavaScript
La propiedad del montón
Esta propiedad puede considerarse una restricción para definir un árbol, una determinada estructura que debe seguirse al construir un árbol. Heap define una relación entre los nodos parentales y sus nodos infantiles, hay dos tipos de montones y, por lo tanto, hay dos tipos de relación que pueden existir entre el nodo principal y el nodo secundario:
- Max-Heap: el valor de los nodos parentales siempre debe ser mayor o igual a los nodos infantiles
- Min-Heap: El valor de los nodos parentales siempre debe ser más pequeño o igual a los nodos infantiles
Una representación del Min-Heap es:
(Imagen de Wikipedia)
Como puede ver, en el árbol los nodos principales tienen valores más bajos que sus nodos infantiles
La representación de AR del Max-Heap es:
(Imagen de Wikipedia)
Puede ver que los nodos principales tienen valores mayores que sus nodos infantiles.
Representación de matriz
Los montones en un lenguaje de programación se representan en forma de una matriz, un ejemplo de la matriz de montón construida desde el árbol máximo de la altura anterior es:
var max-heap = [100,19,36,17,3,25,1,2,7];Al representar un montón binario en forma de matriz, usa la siguiente expresión para deducir lo siguiente:
- Niño izquierdo = i * 2
- Niño correcto = i * 2 + 1
- Padre = I / 2
Dónde "i" significa el índice de la matriz. Hablando de índices, cuando implementamos estructuras de montón usando una matriz, colocamos un "nulo" en el primer índice que es el índice 0.
Representación visual del funcionamiento de un montón
Para una representación virtual del funcionamiento de un mínimo-montón y cómo se insertan los valores en el montón, podemos dirigirnos al visualizador del montón por la Universidad de San Francisco al hacer clic aquí
Inserte valores en el montón y notará cómo se inserta un nuevo elemento en el montón debido a la animación:
Funcionamiento de montón
Un montón binario tiene dos funciones principales:
- Primero es agregar el nuevo elemento en su posición apropiada
- La segunda función es eliminar el valor raíz
Agregar un nuevo elemento en el montón
Siempre se agrega un nuevo elemento al final de la matriz, y luego se verifica contra su padre y si va en contra de la propiedad del montón, entonces se intercambia con su padre. El elemento se verifica hasta que se haya comparado con el nodo raíz del montón (el nodo raíz es el primer nodo del montón).
Eliminar un elemento del montón
Siempre que desee eliminar o obtener un valor del montón, siempre obtiene el valor del nodo raíz. Es por eso que este valor es el valor más pequeño si se trata de un mínimo y el valor más grande si es un máximo de tiempo. Cuando el nodo raíz se retira del montón, el último nodo de la matriz ocupa su lugar, luego se compara con sus nodos infantiles para que coincida con la condición del montón. Si no coincide con la condición, se reemplaza con su nodo secundario y luego se verifica con más nodos infantiles. Una manera mucho mejor de explicar esto es mediante el uso del visor de Heap Live como se muestra a continuación:
Puede observar el proceso de eliminación observando el GIF anterior.
Implementación del montón binario en JavaScript
Vamos a implementar el paso a paso MIN-TAEP, comenzamos el proceso creando una nueva función con las siguientes líneas de código:
Sea minheap = function ()// El resto del código MIN-HAEP estará presente a la inherente
El primer paso es crear una matriz y establecer el valor en el índice 0 como nulo:
Let Heap = [NULL];
Entonces vamos a crear el función de inserción Usando las siguientes líneas de código:
este.insert = function (num)
montón.empuje (num);
if (montón.longitud> 2)
letidx = montón.Longitud - 1;
while (Heap [idx] = 1)
[montón [matemáticas.piso (IDX / 2)], Heap [IDX]] = [
Heap [IDX],
montón [matemáticas.piso (IDX / 2)],
];
Si (matemáticas.piso (IDX / 2)> 1)
IDX = matemáticas.piso (IDX / 2);
demás
romper;
;
Las siguientes cosas están sucediendo en este fragmento de código:
- Un nuevo elemento numer se agrega en el último índice de la matriz
- Si la longitud de la matriz es mayor que 2 elementos, entonces verificamos el nuevo elemento con su nodo principal
- Si el elemento es más pequeño que su nodo principal, entonces se reemplaza con su nodo principal, de lo contrario, deducimos que el montón en orden correcto
- Si el elemento se reemplaza con su nodo principal en el paso anterior, entonces lo comparamos nuevamente con su nuevo padre hasta que deducimos que el montón está en orden correcto o el elemento se convierte en el nodo raíz
El siguiente paso es implementar el eliminar la función Con las siguientes líneas de código:
este.eliminar = function ()Deje más pequeño = montón [1];
if (montón.longitud> 2)
montón [1] = montón [montón.longitud - 1];
montón.empalme (montón.longitud - 1);
if (montón.longitud == 3)
if (Heap [1]> Heap [2])
[Heap [1], Heap [2]] = [Heap [2], Heap [1]];
regresar más pequeño;
leti = 1;
Letleft = 2 * i;
LESTRight = 2 * i + 1;
while (Heap [i]> = Heap [izquierda] || Heap [i]> = Heap [Right])
if (Heap [izquierda] < heap[right])
[Heap [i], Heap [izquierda]] = [Heap [izquierda], Heap [i]];
i = 2 * i;
demás
[Heap [i], Heap [Right]] = [Heap [Right], Heap [i]];
i = 2 * i + 1;
izquierda = 2 * i;
Derecha = 2 * i + 1;
if (Heap [izquierda] == Undefined || Heap [derecho] == Undefined)
romper;
Elseif (montón.longitud == 2)
montón.empalme (1, 1);
demás
regresar nulo;
regresar más pequeño;
;
Los siguientes pasos están sucediendo en el fragmento de código anterior:
- Eliminamos el nodo raíz ya que es el nodo más pequeño del montón
- Si el montón solo tiene dos elementos, entonces el segundo elemento se convierte en el nodo raíz
- Si el montón tiene 3 elementos, el más pequeño fuera del segundo y tercer elemento se convierte en el nodo raíz
- Si el elemento tiene más de 3 elementos, entonces el último elemento del montón se convierte en el nodo raíz
- Luego, este nuevo nodo raíz se compara con sus nodos infantiles y se reemplaza con el nodo más pequeño y está en contra de los nuevos nodos infantiles (para el reemplazo estamos utilizando el Método de destrucción de objetos)
- Este proceso de comparación del elemento con los nodos infantiles se repite hasta que alcanza un punto en el que es más pequeño que los dos nodos infantiles o se convierte en el último nodo en la matriz.
El siguiente paso es crear una función que nos muestre la matriz de montón a la consola, lo hacemos utilizando las siguientes líneas de código:
este.show = function ()consola.log (montón);
;
El fragmento de código completo de la implementación de la estructura de datos MIN-HeAP es:
letminheap = function ()Let Heap = [NULL];
este.insert = function (num)
montón.empuje (num);
if (montón.longitud> 2)
letidx = montón.Longitud - 1;
while (Heap [idx] = 1)
[montón [matemáticas.piso (IDX / 2)], Heap [IDX]] = [
Heap [IDX],
montón [matemáticas.piso (IDX / 2)],
];
Si (matemáticas.piso (IDX / 2)> 1)
IDX = matemáticas.piso (IDX / 2);
demás
romper;
;
este.eliminar = function ()
Deje más pequeño = montón [1];
if (montón.longitud> 2)
montón [1] = montón [montón.longitud - 1];
montón.empalme (montón.longitud - 1);
if (montón.longitud == 3)
if (Heap [1]> Heap [2])
[Heap [1], Heap [2]] = [Heap [2], Heap [1]];
regresar más pequeño;
leti = 1;
dejar a la izquierda = 2 * i;
Let Right = 2 * i + 1;
while (Heap [i]> = Heap [izquierda] || Heap [i]> = Heap [Right])
if (Heap [izquierda] < heap[right])
[Heap [i], Heap [izquierda]] = [Heap [izquierda], Heap [i]];
i = 2 * i;
demás
[Heap [i], Heap [Right]] = [Heap [Right], Heap [i]];
i = 2 * i + 1;
izquierda = 2 * i;
Derecha = 2 * i + 1;
if (Heap [izquierda] == Undefined || Heap [derecho] == Undefined)
romper;
Elseif (montón.longitud == 2)
montón.empalme (1, 1);
demás
Returnnull;
regresar más pequeño;
;
este.show = function ()
consola.log (montón);
;
;
Lo que debemos hacer ahora es crear un nuevo Min-HeAP usando la función Minheap que acabamos de crear y luego agregarle elementos usando el Insertar y mostrar el montón. Para hacer esto, hacemos una nueva variable y la asignamos en el minheap utilizando las siguientes líneas de código:
var newminheap = new Minheap ();A continuación, subamos valores al montón utilizando las siguientes líneas de código:
nuevo.insertar (34);nuevo.insertar (61);
nuevo.insertar (138);
nuevo.insertar (82);
nuevo.insertar (27);
nuevo.insertar (35);
Ahora, llamamos al espectáculo función para mostrar la matriz de montón en la consola:
nuevo.espectáculo();Obtenemos el siguiente resultado en nuestra consola:
Como puede ver, el primer elemento de la matriz es nulo. El resto de los nodos no son más grandes que sus nodos infantiles. Por ejemplo, si tomamos el nodo con el valor 35. El niño izquierdo y derecho son como:
Puedes ver claramente el padre (35) es más pequeño que su hijo izquierdo (82) y su hijo derecho (61) también. Del mismo modo, cada nodo principal es más pequeño que su nodo hijo, por lo tanto, podemos deducir que nuestro código funciona perfectamente
Del mismo modo, simplemente cambiar la condición para comparar para ser el nodo principal que es más pequeño que el niño al nodo principal que es más grande que el nodo secundario, podemos implementar el Montón Usando las siguientes líneas de código:
letmaxHeap = function ()Let Heap = [NULL];
este.insert = function (num)
montón.empuje (num);
if (montón.longitud> 2)
letidx = montón.Longitud - 1;
while (Heap [IDX]> Heap [matemáticas.piso (idx / 2)])
if (idx> = 1)
[montón [matemáticas.piso (IDX / 2)], Heap [IDX]] = [
Heap [IDX],
montón [matemáticas.piso (IDX / 2)],
];
Si (matemáticas.piso (IDX / 2)> 1)
IDX = matemáticas.piso (IDX / 2);
demás
romper;
;
este.eliminar = function ()
Deje más pequeño = montón [1];
if (montón.longitud> 2)
montón [1] = montón [montón.longitud - 1];
montón.empalme (montón.longitud - 1);
if (montón.longitud == 3)
if (Heap [1] < heap[2])
[Heap [1], Heap [2]] = [Heap [2], Heap [1]];
regresar más pequeño;
leti = 1;
dejar a la izquierda = 2 * i;
Let Right = 2 * i + 1;
Mientras (montón [i] <= heap[left] || heap[i] heap[right])
[Heap [i], Heap [izquierda]] = [Heap [izquierda], Heap [i]];
i = 2 * i;
demás
[Heap [i], Heap [Right]] = [Heap [Right], Heap [i]];
i = 2 * i + 1;
izquierda = 2 * i;
Derecha = 2 * i + 1;
if (Heap [izquierda] == Undefined || Heap [derecho] == Undefined)
romper;
Elseif (montón.longitud == 2)
montón.empalme (1, 1);
demás
Returnnull;
regresar más pequeño;
;
este.show = function ()
consola.log (montón);
;
;
Eso es todo, ha implementado con éxito un montones binarios en JavaScript
Conclusión
Los montones binarios son la implementación parietal de un árbol binario que tiene la condición de tener más Dos nodos infantiles para cada nodo principal y la estructura completa del árbol binario. Lo que significa que los niveles del árbol se llenarán desde el lado izquierdo o el hijo izquierdo y luego el niño derecho.
Los montones binarios son parte de las estructuras de datos avanzadas, y hay dos tipos de árbol binario: uno de ellos se llama el montón min, mientras que el otro se llama el montón máximo. En el Min-Heap, los nodos principales tienen valores más pequeños que sus nodos infantiles y los valores de los nodos hermanos no importan.
Del mismo modo, en máximo-heap, los valores del nodo principal son siempre mayores que el nodo de su hijo y los valores de los nodos hermanos no importan. En esta publicación, aprendimos sobre los montones y su implementación en Vanilla JavaScript y al final probamos nuestra implementación.