Ordenar montones en Java

En esta guía, veremos la teoría y la implementación de Heap Sort en Java; lo implementaremos a través de Heap y PriorityQueue.

Introducción

La clasificación es una de las técnicas fundamentales utilizadas en la resolución de problemas, especialmente en aquellos relacionados con la escritura e implementación de algoritmos eficientes.

Por lo general, la clasificación se combina con la búsqueda, lo que significa que primero clasificamos elementos en la colección dada, luego buscamos algo dentro de ella, ya que generalmente es más fácil buscar algo en una colección ordenada, en lugar de una sin clasificar, ya que puede hacer conjeturas informadas e imponer suposiciones sobre los datos.

Hay muchos algoritmos que pueden ordenar elementos de manera eficiente, pero en esta guía veremos cómo implementar Heap Sort en Java.

Para comprender cómo funciona Heap Sort, primero debemos comprender la estructura en la que se basa: el *** montón ***. En este artículo hablaremos específicamente en términos de un montón binario, pero con pequeños ajustes, los mismos principios también pueden generalizarse a otras estructuras de montón.

{.icon aria-hidden=“true”}

Haremos otra implementación sin montones, sino PriorityQueues, que reducen el algoritmo a una sola línea.

Montón como estructura de datos

Un heap es una estructura de datos basada en un árbol especializado que es un árbol binario completo que satisface la propiedad del montón, es decir, para cada nodo, todos sus elementos secundarios están en relación con él. En un montón máximo, para un padre P dado y un hijo C, el valor de P es mayor o igual que el valor del hijo C.

Análogamente, en un min heap, el valor de P es menor o igual que el valor de su hijo C. El nodo en la "superior" del montón (es decir, el nodo que no tiene padres) se llama la raíz.

Aquí hay un ejemplo de un montón mínimo (izquierda) y un montón máximo (derecha):

heap representation

Como mencionamos anteriormente, vemos el montón como una estructura de datos basada en árboles. Sin embargo, lo representaremos con una matriz simple y solo definiremos cómo cada nodo (hijo) se relaciona con su padre. Suponiendo que nuestra matriz comience desde un índice 0, podemos representar el montón máximo de la ilustración anterior con la siguiente matriz:

1
53, 25, 41, 12, 6, 31, 18

También podemos explicar esta representación leyendo el gráfico nivel por nivel, de izquierda a derecha. Esencialmente, hemos definido algún tipo de relación entre un nodo padre y un nodo hijo.

Para el elemento k-th de la matriz, podemos encontrar sus hijos en las posiciones 2*k+1 y 2*k+2, suponiendo que la indexación comience desde 0. De manera similar, podemos encontrar el padre del elemento k-th en la posición (k-1)/2.

Anteriormente mencionamos que el montón es un árbol binario completo. Un árbol binario completo es un árbol binario en el que todos los niveles, excepto posiblemente el último, están completamente llenos y todos los nodos están alineados a la izquierda.

{.icon aria-hidden=“true”}

Nota: Un árbol binario completo puede ser lo mismo que un árbol binario completo, pero en esencia es un concepto diferente, donde un árbol binario completo representa un árbol en el que todos los nodos excepto las hojas tienen exactamente dos hijos.

Para explicar un poco más el concepto de un árbol binario completo, veamos un ejemplo del montón máximo de la ilustración anterior. Si eliminamos los nodos 12 y 6 obtenemos el siguiente árbol binario:

full binary tree

Este árbol se representará en una matriz como:

1
53, 25, 41, -, -, 31, 18

Podemos ver que este no es un árbol binario completo, ya que los nodos en el nivel 2 (si el nodo raíz está en el nivel 0), no están alineados a la izquierda. Mientras que por otro lado, el siguiente árbol binario representaría un árbol binario completo:

complete binary tree

La matriz para este árbol sería:

1
53, 25, 41, 12, 6

Del breve ejemplo anterior, podemos ver que intuitivamente un árbol binario completo se representa con una matriz que no tiene "brechas", es decir, las posiciones que representamos en la primera matriz anterior como -.

Continuando con nuestra explicación del montón, el proceso de inserción y eliminación de elementos es un paso crucial en Heap Sort.

{.icon aria-hidden=“true”}

Nota: Nos centraremos en un montón máximo, pero tenga en cuenta que todo lo que se aplica al montón máximo también se aplica al montón mínimo.

Inserción de un elemento en el montón máximo

Usando el mismo montón máximo que teníamos anteriormente, digamos que queremos agregar el elemento 60. A primera vista, es evidente que 60 sería el elemento más grande de nuestro montón, por lo que debería convertirse en el elemento raíz. Pero eso plantea otra pregunta: ¿cómo mantenemos simultáneamente la forma de un árbol binario completo y agregamos 60 al mismo tiempo?

Comencemos colocando el elemento en la última posición en nuestra matriz de almacenamiento dinámico y obtengamos algo como esto:

1
2
// 0   1   2   3  4   5   6   7
  53, 25, 41, 12, 6, 31, 18, 60

{.icon aria-hidden=“true”}

Los números en la fila de arriba representan las posiciones de índice de la matriz

Como se discutió anteriormente, los hijos del nodo k-ésimo están ubicados en las posiciones 2*k+1 y 2*k+2, mientras que el padre de cada nodo está en (k-1)/2 . Siguiendo el mismo patrón, 60 sería un hijo de 12.

Ahora, esto perturba la forma de nuestro montón máximo, ya que comparar y verificar si “60” es menor o igual que “12” produce una respuesta negativa. Lo que haremos es intercambiar estos dos, ya que estamos seguros de que no hay números menores que ‘60’ en el árbol binario, ya que ‘60’ era una hoja.

Después del intercambio, obtenemos lo siguiente:

1
2
// 0   1   2   3  4   5   6   7
  53, 25, 41, 60, 6, 31, 18, 12

Repetimos el mismo paso que antes hasta que 60 esté en su lugar correcto. El elemento principal de 60 ahora sería 25. Intercambiamos estos dos, después de lo cual el elemento principal de 60 es 53, después de lo cual también los intercambiamos, terminando con un montón máximo:

1
2
// 0   1   2   3  4   5   6   7
  60, 53, 41, 25, 6, 31, 18, 12

Eliminación de un elemento del montón máximo

Ahora, analicemos la eliminación de un elemento. Usaremos el mismo montón máximo que antes (sin la adición de 60). Cuando se habla de eliminar un elemento del montón, la operación de eliminación estándar implica que solo deberíamos eliminar el elemento raíz. En el caso del montón máximo, este es el elemento más grande, y en el caso del montón mínimo, el más pequeño.

Eliminar un elemento del montón es tan simple como eliminarlo de la matriz. Sin embargo, esto crea un nuevo problema ya que la eliminación crea una "brecha" en nuestro árbol binario, por lo que no está completo.

Afortunadamente para nosotros, la solución es igual de simple: reemplazamos el elemento raíz eliminado con el elemento que está más a la derecha en el nivel más bajo en el montón. Hacer esto nos garantiza que tendremos un árbol binario completo una vez más, pero una vez más crea un nuevo problema potencial: aunque nuestro árbol binario ahora está completo, es posible que no sea un montón. Entonces, ¿cómo hacemos para resolver esto?

Analicemos la eliminación de un elemento en el mismo montón máximo que antes (antes de agregar 60). Después de eliminar nuestra raíz y mover nuestro elemento más a la derecha en su lugar, tenemos lo siguiente:

1
2
// 0   1   2   3  4   5  6
  18, 25, 41, 12, 6, 31

{.icon aria-hidden=“true”}

Nota: El elemento en la posición 6 se deja vacío a propósito; esto será importante más adelante.

Representado así, nuestra matriz no es un montón máximo. Lo que debemos hacer a continuación es comparar 18 con sus hijos, específicamente con el mayor de los dos, y en este caso es 41. Si el mayor de los dos hijos es mayor que el padre, intercambiamos los dos.

Después de hacer esto, obtenemos la siguiente matriz:

1
2
// 0   1   2   3  4   5  6
  41, 25, 18, 12, 6, 31

Como 18 está ahora en la posición 2, su único hijo es 31, y dado que el hijo es de nuevo más grande que el padre, los intercambiamos:

1
// 0   1   2   3  4   5  6  41, 25, 31, 12, 6, 18

¡Y así volvemos a tener un montón máximo!

Complejidad temporal de inserción y eliminación {#complejidad temporal de inserción y eliminación}

Echemos un vistazo a la complejidad temporal de insertar y eliminar elementos de un montón antes de implementar el algoritmo. Dado que estamos trabajando con una estructura de árbol binario, es natural que la complejidad temporal tanto de la inserción como de la eliminación sea O(logn), donde n representa el tamaño de nuestra matriz.

Esto se debe a que para un árbol binario de altura h, dada la naturaleza binaria del montón: al atravesar hacia abajo el árbol, solo podrá elegir entre dos opciones, reduciendo las posibles rutas por dos en cada paso. En el peor de los casos, al atravesar hacia abajo hasta la parte inferior del árbol, la altura del árbol, h, será logn.

Con esto finalizamos la explicación sobre el montón como estructura de datos y pasamos al tema principal del artículo: Ordenar montón.

Heap Sort en Java

Aprovechando el montón y sus propiedades, lo hemos expresado como una matriz. Podemos fácilmente max heapify cualquier matriz. Max heapify-ing es un proceso de disposición de los elementos en el orden correcto para que sigan la propiedad max heap. Del mismo modo, puede min heapify una matriz.

Para cada elemento, debemos verificar si alguno de sus hijos es más pequeño que él mismo. Si lo son, intercambie uno de ellos con el padre y repita recursivamente este paso con el padre (porque el nuevo elemento grande aún podría ser más grande que su otro hijo). Las hojas no tienen hijos, por lo que ya son montones máximos por sí mismas.

Veamos la siguiente matriz:

1
2
// 0   1  2   3   4   5   6  
   25, 12, 6, 41, 18, 31, 53

Ejecutemos rápidamente el algoritmo heapify a través de él y hagamos un montón a partir de esta matriz, manualmente, y luego implementemos el código en Java para que lo haga por nosotros. Comenzamos desde la derecha y vamos todo el camino hacia la izquierda:

1
25 12 *6* 41 18 **31** **53** 

Dado que 31 > 6 y 53 > 6, tomamos el mayor de los dos (en este caso, 53) y lo intercambiamos con su padre, y obtenemos lo siguiente: 25 12 *53 * 41 18 31 6.

1
25 *12* 6 **41** **18** 31 6 

Una vez más, 18 > 12 y 41 > 12, y dado que 41 > 18, intercambiamos 42 y 12.

1
*25*, **41**, **53** 12, 18, 31, 6 

En este último paso del camino, vemos que ‘41 > 25’ y ‘53 > 25’, y dado que ‘53 > 41’, intercambiamos ‘53’ y ‘25’. Después de eso, acumulamos recursivamente para 25.

1
53, 41, *25*, 12, 18, **31**, **6** 

31 > 25, así que los intercambiamos.

1
53, 41, 31, 12, 18, 25, 6 

¡Tenemos un montón máximo! Sin embargo, este proceso puede parecer desalentador: cuando se implementa en el código, en realidad es bastante simple. El proceso de heapyfing es crucial para Heap Sort, que sigue tres pasos:

1. Cree una matriz de almacenamiento dinámico máximo utilizando la matriz de entrada.
2. Dado que el montón máximo almacena el elemento más grande de la matriz en la parte superior (es decir, el comienzo de la matriz), debemos intercambiarlo con el último elemento dentro de la matriz, y luego reducir el tamaño de la matriz (montón) por 1. Después de eso, amontonamos la raíz.
3. Repetimos el paso 2 siempre que el tamaño de nuestro montón sea mayor que 1.

Con una buena intuición de cómo funciona el algoritmo, podemos llegar a implementarlo. En general, dado que llamaremos a un método heapify() varias veces, lo implementamos por separado del método heapsort() y lo llamamos dentro de él.

Esto hace que la implementación sea más limpia y fácil de leer. Empecemos con el método heapify():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public static void heapify(int[] array, int length, int i) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < length && array[left] > array[largest]) {
        largest = left;
    }
    if (right < length && array[right] > array[largest]) {
        largest = right;
    }
    if (largest != i) {
        int tmp = array[i];
        array[i] = array[largest];
        array[largest] = tmp;
        heapify(array, length, largest);
    }
}

El método heapify() es lo que hace la mayor parte del trabajo pesado, y solo consta de tres sentencias if. El flujo del algoritmo Heap Sort también es bastante simple y se basa principalmente en heapify():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public static void heapSort(int[] array) {
    if (array.length == 0) {
        return;
    }
    
    int length = array.length;
    
    // Moving from the first element that isn't a leaf towards the root
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(array, length, i);
    }
    
    for (int i = length - 1; i >= 0; i--) {
        int tmp = array[0];
        array[0] = array[i];
        array[i] = tmp;
        heapify(array, i, 0);
    }
}

¡Eso es todo! Ahora podemos proporcionar una matriz al método heapSort(), que lo ordena en el lugar:

1
2
3
4
5
public static void main(String[] args){
    int[] array = {25, 12, 6, 41, 18, 31, 53};
    heapSort(array);
    System.out.println(Arrays.toString(array));
}

Esto resulta en:

1
[6, 12, 18, 25, 31, 41, 53]

Implementación de Heap Sort con una cola de prioridad

Una Cola de prioridad es una estructura de datos que en realidad es un tipo específico de una cola, en la que los elementos se agregan con una prioridad uno por uno, de ahí el nombre. La eliminación de elementos comienza con el que tiene la prioridad más alta. La definición en sí es muy similar a la de un montón, por lo que es natural que también pueda implementar Heap Sort usando esta estructura de datos muy conveniente.

Java tiene un PriorityQueue incorporado que reside en el paquete util:

1
import java.util.PriorityQueue;

PriorityQueue tiene bastantes métodos propios y heredados de la interfaz Queue, pero para nuestros propósitos solo necesitaremos usar algunos:

  • boolean add(E e) - inserta el elemento e en la cola de prioridad.
  • E poll() - recupera y elimina el encabezado de la cola de prioridad, o devuelve null si está vacío.
  • int size() - devuelve el número de elementos en la cola de prioridad.

Con estos, realmente podemos implementar Heap Sort a través de un solo bucle while().

En primer lugar, crearemos y agregaremos los elementos a la cola de prioridad, después de lo cual simplemente ejecutaremos un bucle while siempre que nuestra cola de prioridad pq tenga al menos 1 elemento dentro. En cada iteración, usamos el método poll() para recuperar y eliminar el encabezado de la cola, después de lo cual lo imprimimos y producimos el mismo resultado que antes:

1
2
3
4
5
6
7
Queue<Integer> pq = new PriorityQueue<>();
int[] array = new int[]{25, 12, 6, 41, 18, 31, 53};
Arrays.stream(array).forEach(element -> pq.add(element));

while(pq.size() > 0){
    System.out.print(pq.poll() + " ");
}

Esto resulta en:

1
6 12 18 25 31 41 53 

Complejidad temporal de Heapsort

Discutamos la complejidad temporal de los dos enfoques que hemos cubierto.

Hemos discutido anteriormente que agregar y eliminar elementos de un montón requiere tiempo O (logn), y dado que nuestro ciclo for se ejecuta n veces donde n es el número de elementos en la matriz, el tiempo total La complejidad de Heapsort implementada de esta manera es O(nlogn). Por otro lado, tanto agregar como quitar los elementos de una cola de prioridad ocupa O(logn) también, y hacer esto n veces también produce complejidad de tiempo O(nlogn).

¿Qué pasa con la complejidad del espacio? Bueno, dado que en ambos enfoques solo estamos usando la matriz inicial para ordenar la matriz, eso significa que el espacio adicional requerido para Heap Sort es O (1), lo que hace que Heap Sort sea un algoritmo en el lugar.

Conclusión

En conclusión, este artículo ha cubierto tanto la teoría como la implementación detrás del algoritmo Heap Sort. Comenzamos con una explicación de cómo funciona, con una iteración manual intuitiva, seguida de dos implementaciones.

Si bien no es tan rápido en comparación con algo como Ordenación rápida o Ordenar por fusión, Heap Sort se usa a menudo cuando los datos está parcialmente ordenado o cuando se necesita un algoritmo estable. El aspecto en el lugar de Heap Sort también nos permite un mejor uso de la memoria, cuando la memoria es motivo de preocupación.

Licensed under CC BY-NC-SA 4.0