Pilas binarias y colas de prioridad mediante JavaScript

Aunque estoy seguro de que todos podemos estar de acuerdo en que las colas son lo mejor desde que se inventó el pan de molde, en realidad podemos hacerlo mucho mejor si las combinamos con una variación de árboles denominada montículos. Con los montículos podemos estructurar nuestros datos en una cola más inteligente que se ordena por importancia en lugar de por orden.

Conceptos

A diferencia de los árboles de búsqueda binarios, donde comparamos y organizamos nuestros valores entre hermanos, con los montones solo trabajamos entre padres e hijos. Esto nos da dos posibilidades para los montones, el max heapy el min heap, ya sea que se esté moviendo desde los valores más altos a los más bajos o viceversa. Para simplificar, solo nos centraremos en el montón máximo, ya que es muy fácil convertirlo en un montón mínimo.

Al igual que con los árboles de búsqueda binarios, los montículos binarios solo pueden tener dos o menos hijos de un padre. También son especiales porque siempre están equilibrados porque cada nuevo nodo se agregará a un nivel de izquierda a derecha hasta que se complete.

Lamentablemente, las listas enlazadas generalmente no son el mejor enfoque para los montones binarios, a pesar de que generalmente se las conceptualiza como un árbol con hijos izquierdo y derecho, aunque aún es posible.

La mayoría de las veces será mejor manejarlo como una matriz, por eso es lo que vamos a cubrir aquí. El orden es el esperado, con todo de izquierda a derecha en un nivel antes de pasar al siguiente nivel.

De esta manera, creamos un patrón muy consistente para encontrar los hijos de un nodo. Todos los hijos izquierdos de un nodo estarán exactamente en una posición 2n + 1alejada de su padre, nsiendo el índice de su padre, y todos los hijos derechos serán 2n + 2.

Agregar nodo

Parecería que agregar un nuevo nodo sería tan simple como insertarlo en nuestra matriz, pero la parte complicada es que necesitamos compararlo con los padres entre él mismo y el máximo, y luego reordenarlos en consecuencia.

Gráficos/Animación gracias a VisuAlgo.net

Después de insertar nuestro nuevo elemento al final de la matriz, necesitaremos "hacer que emerjan" nuestros valores más grandes. Primero, necesitamos tomar el nuevo elemento al final de la matriz, que dividiremos en el índice y el nuevo elemento en ese índice.

Cada vez que agregamos un elemento, vamos a utilizar la inversa de nuestra ecuación para encontrar hijos, (n-1)/2, para encontrar su padre. Si su padre es menor que el nodo actual, intercámbialos y luego guarda su índice, que será el siguiente current. Esto continuará hasta que no queden padres.

Dado que se irá moviendo gradualmente hacia indexarriba desde el final, siempre que sea mayor que cero, siga intercambiando.

class BH {  constructor() {    this.values = [];  }  add(element) {    this.values.push(element);    let index = this.values.length - 1;    const current = this.values[index];    while (index  0) {      let parentIndex = Math.floor((index - 1) / 2);      let parent = this.values[parentIndex];      if (parent = current) {        this.values[parentIndex] = current;        this.values[index] = parent;        index = parentIndex;      } else break;    }  }}const tree = new BH();tree.add(3);tree.add(4);tree.add(31);tree.add(6);console.log(tree); // [31, 6, 4, 3]

Quitar Max

Quitar el nodo superior es un poco más complicado de lo que crees. Vamos a devolver el primer nodo, nuestro máximo, luego tomaremos el último nodo, el final de nuestra matriz, y lo estableceremos como el nuevo máximo.

Lo hacemos para poder usar nuestro valor más bajo como una línea de base fácil para comparar con nuestros otros valores a medida que “nos hundimos” de nuevo hasta el fondo del árbol mientras hacemos nuestras comparaciones e intercambios en el camino.

Gráficos/Animación gracias a VisuAlgo.net

La parte simple es tomar nuestro valor máximo actual y quitarlo antes de reemplazarlo con el último elemento, luego podemos regresar a nuestro valor máximo original después de que todo lo demás esté hecho.

Una vez que tenemos un índice inicial, queremos capturar tanto sus elementos secundarios derecho como izquierdo. Si el elemento secundario izquierdo es un elemento válido y es más grande, podemos guardarlo para swapejecutar el intercambio cuando se hayan realizado todas las comparaciones.

El hijo correcto es un poco más complicado, solo queremos que uno, y el más grande, se intercambie con el padre. Agregaremos un requisito separado que rightChildsolo se puede configurar como swapsi aún no se hubiera definido o si fuera más grande que leftChild.

class BH {  extractMax() {    const max = this.values[0];    const end = this.values.pop();    this.values[0] = end;    let index = 0;    const length = this.values.length;    const current = this.values[0];    while (true) {      let leftChildIndex = 2 * index + 1;      let rightChildIndex = 2 * index + 2;      let leftChild, rightChild;      let swap = null;      if (leftChildIndex  length) {        leftChild = this.values[leftChildIndex];        if (leftChild  current) swap = leftChildIndex;      }      if (rightChildIndex  length) {        rightChild = this.values[rightChildIndex];        if (          (swap === null  rightChild  current) ||          (swap !== null  rightChild  leftChild)        )          swap = rightChildIndex;      }      if (swap === null) break;      this.values[index] = this.values[swap];      this.values[swap] = current;      index = swap;    }    return max;  }}const tree = new BH();tree.add(3);tree.add(4);tree.add(31);tree.add(6);console.log(tree.extractMax()); // 31

Colas de prioridad

Con unos pocos ajustes menores podemos mezclar montones binarios con colas y crear un tipo de cola que organiza nuestros datos por importancia en lugar de por cuándo se agregaron.

Podemos lograr esto de manera bastante simple almacenando nodos en lugar de números individuales. Cada nodo tendrá un nivel de prioridad (digamos de 1 a 5), ​​que utilizará para determinar el orden. Cuando las prioridades en dos nodos son las mismas, el hijo izquierdo, dado que se habrá agregado primero, irá primero.

Todo lo que tenemos que hacer es utilizar los nodos prioritycada vez que hagamos una comparación en una ifdeclaración.

class Node {  constructor(val, priority) {    this.val = val;    this.priority = priority;  }}class PQ {  constructor() {    this.values = [];  }  enqueue(val, priority) {    let newNode = new Node(val, priority);    this.values.push(newNode);    let index = this.values.length - 1;    const current = this.values[index];    while (index  0) {      let parentIndex = Math.floor((index - 1) / 2);      let parent = this.values[parentIndex];      if (parent.priority = current.priority) {        this.values[parentIndex] = current;        this.values[index] = parent;        index = parentIndex;      } else break;    }  }  dequeue() {    const max = this.values[0];    const end = this.values.pop();    this.values[0] = end;    let index = 0;    const length = this.values.length;    const current = this.values[0];    while (true) {      let leftChildIndex = 2 * index + 1;      let rightChildIndex = 2 * index + 2;      let leftChild, rightChild;      let swap = null;      if (leftChildIndex  length) {        leftChild = this.values[leftChildIndex];        if (leftChild.priority  current.priority) swap = leftChildIndex;      }      if (rightChildIndex  length) {        rightChild = this.values[rightChildIndex];        if (          (swap === null  rightChild.priority  current.priority) ||          (swap !== null  rightChild.priority  leftChild.priority)        )          swap = rightChildIndex;      }      if (swap === null) break;      this.values[index] = this.values[swap];      this.values[swap] = current;      index = swap;    }    return max;  }}const tree = new BH();tree.enqueue(3, 2);tree.enqueue(4, 5);tree.enqueue(31, 1);tree.enqueue(6, 3);console.log(tree.dequeue()); // 4console.log(tree.dequeue()); // 6console.log(tree.dequeue()); // 3console.log(tree.dequeue()); // 31

Reflexiones finales

Al igual que usamos colas estándar para recorrer árboles, las colas de prioridad serán esenciales para recorrer de manera inteligente gráficos y estructuras más complicadas.

Convertir un montón máximo en un montón mínimo es tan simple como cambiar nuestro signo mayor que a menor que en todas nuestras comparaciones.