Ordenar montón en JavaScript

En esta guía detallada, veremos la teoría subyacente y cómo implementar Heap Sort en JavaScript, con código práctico.

Introducción

En esta guía, exploraremos Heap Sort: la teoría detrás de esto y cómo implementar Heap Sort en JavaScript.

Comenzaremos con la estructura de datos en la que se basa (un gran presagio aquí: ¡es un montón!), cómo realizar operaciones en esa estructura de datos y cómo esa estructura de datos se puede usar como medio de un algoritmo de clasificación eficiente.

Las estructuras de datos y los algoritmos de clasificación son conceptos centrales en la programación. Un programa de computadora maneja constantemente grandes conjuntos de datos, recuperando e inyectando datos hasta la saciedad. La forma en que organizamos estos conjuntos de datos y operamos con ellos es de gran importancia, ya que afecta directamente la facilidad y la velocidad con la que el usuario interactúa con nuestras aplicaciones.

Un algoritmo de clasificación se evalúa en función de dos características: el tiempo y el espacio que utiliza el algoritmo en función del tamaño del conjunto de datos. Estos se conocen como Complejidad de tiempo y Complejidad de espacio respectivamente, y nos permiten "enfrentar" los algoritmos entre sí en escenarios promedio y en el mejor de los casos.

{.icon aria-hidden=“true”}

Heap Sort se considera un algoritmo eficiente, con una complejidad de tiempo promedio de θ(n log(n)).

Aunque existen otros algoritmos que superan a Heap Sort en el escenario promedio, su importancia se basa en su poder para funcionar con la misma eficacia en el peor de los casos como lo hace en el mejor, lo que le brinda un tiempo de ejecución estable en conjuntos de datos variables, mientras que algunos algoritmos puede sufrir de grandes o pequeños - dependiendo de su mecanismo subyacente.

Ordenación en montón en JavaScript

Heap Sort es un algoritmo de clasificación in situ, no estable y basado en comparaciones.

No requiere estructuras de datos auxiliares: ordena los datos in situ y afecta a los datos originales (in situ). No conserva el orden relativo o elementos iguales. Si tiene dos elementos con el mismo valor en una colección sin ordenar, su orden relativo puede cambiar (o permanecer igual) en la colección ordenada (no estable). Finalmente, los elementos se comparan entre sí para encontrar su orden (basado en comparación).

Aunque Heap Sort está en su lugar (no requiere una estructura de datos auxiliar), para que la implementación sea un poco clara, reclutaremos una matriz adicional durante la clasificación.

El mecanismo subyacente a Heap Sort es bastante simple y algunos incluso lo llaman "Clasificación de selección mejorada".

If you'd like to read more about Selection Sort, read our Ordenar por selección en JavaScript!

Comienza convirtiendo la matriz no ordenada en un montón, ya sea un montón máximo o un montón mínimo. En el caso de un montón máximo, cada padre tiene un valor mayor que sus descendientes, lo que hace que el elemento raíz sea el más grande entre el montón y viceversa.

Heap Sort se basa en esta condición de montón.

En cada iteración, el algoritmo elimina la raíz del montón y la coloca en una matriz vacía. Después de cada eliminación, el montón se restaura a sí mismo, burbujeando su segundo elemento más grande (o el segundo más pequeño) hasta la raíz para preservar su condición de montón. Este proceso también se conoce como heapificación y, a menudo, verá que las personas se refieren a los métodos que hacen esto como heapificación.

Heap Sort continúa desplazando los elementos raíz recién ubicados en la matriz ordenada hasta que no quede ninguno.

El uso de un montón máximo de esta manera dará como resultado una matriz con elementos en orden descendente. Para que la matriz esté en orden ascendente, se debe optar por un montón mínimo.

Este tipo de autoclasificación y eliminación selectiva recuerda a la clasificación por selección (sin la parte de autoclasificación), por lo tanto, las personas dibujan paralelos.

¿Qué es un montón? {#lo que es un montón}

Un montón es una estructura de datos similar a un árbol. El tipo de montón que usaremos para nuestros propósitos será un árbol binario (una estructura de datos que se asemeja a una rama de árbol y está obligada a comenzar con un nodo y, si tuviera que ramificarse, se permite un máximo de dos sucesores que se extiendan desde cada nodo ). Si bien existen pocos tipos de montones, hay dos características distintivas de un montón:

  1. Un montón debe estar completo, lo que significa que cada nivel del árbol debe llenarse de izquierda a derecha, y no se permite crear otro nivel del árbol sin llenar todos los nodos posibles que quedan en el último nivel.

heap data structure

  1. Cada nodo debe tener un valor mayor o igual (en el caso de un montón mínimo, menor o igual) al valor de cada uno de sus descendientes. Esto se denomina "condición de montón".

Asignación de un montón a una matriz

Lo que hemos definido y representado como un montón hasta este punto es simplemente un diagrama, una colección de círculos y líneas. Para usar esta estructura en un programa de computadora basado en JavaScript, necesitamos volver a trabajar en una matriz o una lista.

Afortunadamente, esta es una operación bastante sencilla que imita la forma en que construimos el montón en primer lugar. Leemos y cambiamos los elementos del montón a una matriz en el mismo orden en que los colocamos en el montón: de izquierda a derecha y nivel por nivel.

Un ejemplo de un montón y su equivalente de matriz, después de este cambio:

heap to array data structure

De esta manera, no solo podemos lograr expresar un montón en código, sino que también obtenemos una brújula con la que navegar dentro de ese montón. Podemos deducir tres ecuaciones que, dado el índice de cada nodo, nos indicarán la ubicación de su padre y sus hijos derecho e izquierdo dentro de la matriz:

heap to array data structure

Creación de un montón en JavaScript

Ahora que tenemos una definición detallada de un montón, podemos seguir adelante e implementarlo como una clase de JavaScript.

En esta guía, crearemos y emplearemos un montón máximo. Dado que la diferencia entre un montón máximo y un montón mínimo es trivial y no afecta la lógica general detrás del algoritmo Heap Sort, la implementación del montón mínimo y, por lo tanto, la creación de un orden ascendente a través de la clasificación del montón es un asunto de cambiar los operadores de comparación.

Avancemos y definamos una clase MaxHeap:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class MaxHeap{
    constructor(){
        this.heap = [];
    }

    parentIndex(index){
        return Math.floor((index-1)/2);
    }

    leftChildIndex(index){
        return (2*index + 1);
    }

    rightChildIndex(index){
        return (2*index + 2);
    }
}

En la clase MaxHeap, hemos definido un constructor que inicializa una matriz vacía. Más adelante, crearemos funciones adicionales para llenar un montón dentro de esta matriz.

Sin embargo, por el momento, solo hemos creado funciones auxiliares que devolverán el índice del padre y los hijos de un nodo determinado.

Inserción de elementos en un montón

Cada vez que se inserta un nuevo elemento en un montón, se coloca junto al nodo más a la derecha en el nivel inferior (el último espacio vacío en la representación de matriz) o, si el nivel inferior ya está lleno, en el nodo más a la izquierda de un nuevo nivel . En este escenario, se garantiza el primer requisito del montón: la integridad del árbol.

En el futuro, la propiedad del montón, que probablemente se haya alterado, debe restablecerse. Para mover el nuevo elemento a su lugar adecuado en el montón, se compara con su padre y, si el nuevo elemento es más grande que su padre, los elementos se intercambian.

El nuevo elemento se burbujea en el montón, mientras se compara con su padre en cada nivel hasta que finalmente se restaura la propiedad del montón:

representación en matriz de un montón en javascript

Agreguemos esta funcionalidad a la clase MaxHeap que hemos creado previamente:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 swap(a, b) {
        let temp = this.heap[a];
        this.heap[a] = this.heap[b];
        this.heap[b] = temp;
    }

 insert(item) {
    this.heap.push(item);
    var index = this.heap.length - 1;
    var parent = this.parentIndex(index);
    while(this.heap[parent] && this.heap[parent] < this.heap[index]) {
        this.swap(parent, index);
        index = this.parentIndex(index);
        parent = this.parentIndex(index);
    }
}

swap() se agrega como un método de ayuda para ahorrarnos cierta redundancia en el código, ya que al insertar el nuevo elemento, es posible que tengamos que realizar esta acción varias veces: un número entre cero y log(n) (en el caso en el que el nuevo elemento es más grande que la raíz del montón, y tenemos que hacer que suba todo el árbol que tiene una altura de * log (el-número-total-de-sus-elementos) * - que en otras palabras , es mucho*.

insert() funciona de la siguiente manera:

  1. Agrega el elemento dado al heap utilizando el método JavaScript integrado: push().
  2. Marca el último elemento del ‘montón’ como ‘índice’ y su padre como ‘padre’.
  3. Si bien existe un elemento del montón en el índice padre (this.heap[parent]), y ese elemento resulta ser más pequeño que el del index (this.heap[parent] < this.heap[index), el método insert() pasa a intercambiar los dos (this.swap(parent, index)) y mueve el cursor un nivel hacia arriba.

Eliminación de elementos del montón

Un montón solo permite la eliminación del elemento raíz, lo que nos deja con un montón completamente distorsionado. A continuación, primero tenemos que restablecer la propiedad árbol binario completo moviendo el último nodo del montón a la raíz. Luego necesitamos burbujear este valor fuera de lugar hasta que la propiedad del montón vuelva a estar en su lugar:

eliminando elementos del montón para ordenar en montón en javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
delete() {
    var item = this.heap.shift();
    this.heap.unshift(this.heap.pop());
    var index = 0;
    var leftChild = this.leftChildIndex(index);
    var rightChild = this.rightChildIndex(index);
    while(this.heap[leftChild] && this.heap[leftChild] > this.heap[index] || this.heap[rightChild] > this.heap[index]){
        var max = leftChild;
        if(this.heap[rightChild] && this.heap[rightChild] > this.heap[max]){
            max = rightChild
        }
        this.swap(max, index);
        index = max;
        leftChild = this.leftChildIndex(max);
        rightChild = this.rightChildIndex(max);
    }
    return item;
}

El método delete(), que creamos dentro de la clase MaxHeap, funciona de la siguiente manera:

  1. El método comienza recolectando el elemento más grande, por lo tanto, el primer elemento en la representación de matriz del montón. El método integrado shift() elimina el primer elemento de la matriz y devuelve el elemento eliminado, que luego almacenamos en la variable item.
  2. El último elemento del heap se elimina mediante pop() y se coloca en el primer espacio recientemente vaciado del heap mediante unshift(). unshift() es un método JavaScript incorporado que funciona como la contraparte de shift(). Mientras que shift() elimina el primer elemento de la matriz y desplaza el resto de los elementos un espacio hacia atrás, unshift() empuja un elemento al principio de la matriz y desplaza el resto de los elementos un espacio hacia adelante.
  3. Para poder burbujear la nueva raíz hacia abajo, apunta a su ubicación, que inicialmente es 0, y se crean sus dos hijos (index, rightChild, leftChild).
  4. El bucle while() comprueba si existe un hijo izquierdo en el nodo index para garantizar la existencia de otro nivel por debajo (todavía no comprueba si hay un hijo derecho) y si alguno de los hijos en este nivel es más grande que el nodo en [index].
  5. Si se cumple la condición dentro del ciclo while, se crea una variable max para declarar que el nodo izquierdo es el valor máximo que el método ha encontrado hasta ahora. Luego, dentro del ciclo, en una cláusula si, verificamos si existe un hijo derecho y, si existe, si es más grande que el hijo izquierdo que verificamos primero. Si el valor del hijo derecho es realmente mayor, su índice reemplaza el valor en max.
  6. Cualquier hijo que tenga el valor más grande se intercambia con su padre a través de this.swap(max, index).
  7. El método mueve su cursor imaginario un nivel hacia abajo al final del ciclo while y continúa ejecutando el código dentro del ciclo while una y otra vez hasta que su condición ya no se cumple.

Implementando Heap Sort en JavaScript

Finalmente, para lograr lo que promete esta guía, creamos una función heapSort() (esta vez fuera de la clase MaxHeap), y le proporcionamos una matriz que nos gustaría ordenar:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function heapSort(arr){
    var sorted = [];
    var heap1 = new MaxHeap();
    
    for(let i=0; i<arr.length; i++){
        heap1.insert(arr[i]);
    }
    
    for(let i=0; i<arr.length; i++){
        sorted.push(heap1.delete());
    }
    return sorted;
}

heapSort() toma la matriz a ordenar como su argumento. Luego, crea una matriz vacía para colocar la versión ordenada, así como un montón vacío a través del cual realizar la clasificación.

Luego, heap1 se llena con los elementos de arr y se eliminan uno por uno, empujando los elementos eliminados a la matriz ordenada. El heap1 se autoorganiza con cada eliminación, por lo que simplemente empujar los elementos fuera de él en la matriz ordenada nos da una red ordenada.

Vamos a crear una matriz y probar esto:

1
2
3
4
let arr = [1, 6, 2, 3, 7, 3, 4, 6, 9];
arr = heapSort(arr);

console.log(arr);

Conclusión

En esta guía, hemos aprendido sobre la estructura de datos del montón y cómo funciona Heap Sort.

Si bien no es el algoritmo más rápido posible, Heap Sort puede ser ventajoso cuando los datos se ordenan parcialmente o cuando se necesita un algoritmo estable.

Aunque lo hemos implementado utilizando una estructura de datos adicional, Heap Sort es esencialmente un algoritmo de clasificación en el lugar y, por esa razón, también se puede usar en momentos en que el uso de la memoria es una preocupación. a preocupación.