Heapify All The Things With Heap Sort
Alguien me dijo una vez que todo lo importante en informática se reduce a árboles. Literalmente, sólo árboles. Podemos usarlos para construir cosas, parsear cosas e interpretar cosas (sí, puede que haya algún tipo de presagio aquí, no te preocupes si no tiene ningún sentido para ti todavía, porque pronto lo tendrá). E incluso podemos utilizarlas para -¡adivinaste! – ordenar cosas.
Ah, ordenar. Hemos hecho mucho en las últimas semanas, pero ahora estamos llegando al final de nuestras aventuras de clasificación. Sin embargo, es imposible e injusto hablar de la ordenación sin hablar de un tipo especial de ordenación que utiliza la estructura de datos más reciente en nuestro cinturón de herramientas de estructuras de datos.
Recientemente hemos aprendido a amar los heaps, un tipo especial de árbol binario que sigue un conjunto estricto de reglas, y se utilizan para implementar cosas como colas de prioridad y trabajos en segundo plano. Pero estas no son las únicas cosas para las que los heaps son buenos. Resulta que los montones binarios se utilizan a menudo con el único propósito de ordenar eficientemente. Muchos programas se basan en la ordenación del montón ya que resulta ser una de las formas más eficientes de ordenar un array. Y ahora que sabemos lo que es un montón, podemos tratar de entender por qué funciona tan bien cuando se trata del problema de la ordenación!
Antes de sumergirnos en la ordenación por montón, vamos a asegurarnos de que tenemos los montones claros en nuestras cabezas. Recordemos que un montón no es más que un árbol binario con algunas reglas adicionales que tiene que seguir: en primer lugar, siempre debe tener una estructura de montón, donde todos los niveles del árbol binario se llenan, de izquierda a derecha, y en segundo lugar, debe ser ordenado como un montón máximo o un montón mínimo. Para los propósitos de la ordenación del montón, trataremos exclusivamente con montones máximos, donde cada nodo padre (incluyendo la raíz) es mayor o igual que el valor de sus nodos hijos.
Muy bien, vamos a responder a la pregunta del momento: ¿cómo ordenamos usando montones? Bueno, para responder a esa pregunta, primero tenemos que entender lo que es un algoritmo de ordenación en montón.
Un algoritmo de ordenación en montón es una técnica de ordenación que se apoya en estructuras de datos binarias en montón. Como sabemos que los montones deben seguir siempre un orden específico, podemos aprovechar esa propiedad y utilizarla para encontrar el elemento de mayor valor, y ordenar secuencialmente los elementos seleccionando el nodo raíz de un montón, y añadiéndolo al final del array.
Ya sabemos que la ordenación en el montón es una forma eficiente de ordenar un array no ordenado; pero ¿qué tiene que ver un array con un montón? ¿Y cómo podemos ordenar un array utilizando un montón? Bueno, hay tres pasos clave para que esto funcione en la práctica. Los veremos más a fondo en un momento, pero primero echemos un vistazo a lo que son estos tres pasos.
- Para empezar, tenemos un array sin ordenar. El primer paso es tomar ese array y convertirlo en un montón; en nuestro caso, querremos convertirlo en un montón máximo. Así que tenemos que transformar y construir un montón máximo a partir de los datos de nuestro array sin clasificar. Normalmente, esto se encapsula en una sola función, que podría llamarse algo así como
buildMaxHeap. - Una vez que tenemos nuestros datos de matriz en un formato de montón máximo, podemos estar seguros de que el valor más grande está en el nodo raíz del montón. Recuerda que, aunque todo el montón no estará ordenado, si hemos construido nuestro max heap correctamente y sin errores, cada nodo padre de nuestro montón tendrá un valor mayor que sus hijos. Así que moveremos el valor más grande -situado en el nodo raíz- al final del montón intercambiándolo con el último elemento.
- Ahora, el elemento más grande del montón se encuentra en el último nodo, lo cual es genial. Sabemos que está en su posición ordenada, por lo que puede ser eliminado del montón por completo. Pero aún queda un paso más: ¡asegurarnos de que el nuevo elemento del nodo raíz está en el lugar correcto! Es muy poco probable que el elemento que intercambiamos en la posición del nodo raíz esté en el lugar correcto, así que moveremos el elemento del nodo raíz hacia abajo hasta su lugar correcto, usando una función que normalmente se llama algo así como
heapify.
¡Y eso es básicamente todo! El algoritmo continúa repitiendo estos pasos hasta que el montón se reduce a un solo nodo. En ese momento, sabe que todos los elementos de la matriz sin ordenar están en sus posiciones ordenadas, y que el último nodo que queda acabará siendo el primer elemento de la matriz ordenada.
Muy bien, sé que he dicho que estos son los tres únicos pasos para ordenar el montón. Pero si estos tres pasos parecen confusos, no te preocupes; pueden ser bastante complicados y difíciles de entender hasta que los ves en acción. De hecho, creo que este algoritmo tiene mucho más sentido con un ejemplo ilustrado. Como los montones son un tipo de árbol, ayuda a visualizarlos, de la misma manera que lo hacemos con los árboles binarios.
¿Has mirado alguna vez bajo el capó de la ordenación de montones?
De acuerdo, es el momento de mi parte favorita para aprender la ordenación de montones: ¡dibujarla! ¡Hurra! Para entender lo que ocurre bajo el capó de la ordenación en montón, trabajaremos con un pequeño conjunto de datos sin ordenar.
Empezaremos con un array sin ordenar con cinco elementos que están súper desordenados: .
Recuerda que, dado que estamos trabajando con la ordenación en montón, vamos a tener que convertir ese array en un montón, para empezar.
En la ilustración que se muestra aquí, puedes ver que el array se ha transformado en un árbol – ¡todavía no es un montón porque todavía no está en ningún orden máximo o mínimo del montón! Podemos ver que este es el caso porque 3 no es el elemento más grande o más pequeño, y sin embargo, es el nodo raíz en este momento. Esto es sólo un árbol, con los elementos del array directamente traducidos a un formato de árbol binario.
Pero, como necesitamos tratar con un max heap, tendremos que transformar nuestra estructura de un árbol binario a un max heap. Fíjate en que, en el montón máximo, los nodos padre son todos más grandes que sus hijos. La semana pasada, aprendimos los algoritmos que nos permiten determinar los nodos hijos a partir del índice de un array; esta semana, los veremos en acción. Esos algoritmos son los que estamos utilizando para transformar este array en un árbol, y luego en un montón.
Bien, ahora tenemos un montón máximo real. Genial. Ahora toca ordenar.
Como sabemos que el elemento más grande está en el nodo raíz, sabemos que tendremos que ponerlo al final del array, en el último lugar de índice disponible. Así que cambiaremos el nodo raíz por el último nodo. Una vez que hagamos este intercambio, nuestro último nodo contendrá el elemento de valor máximo más grande.
¡Bien! Ahora podemos ver que 19, el elemento más grande, que solía ser el nodo raíz, está ahora en la última posición del array. ¡Y, puesto que está efectivamente «ordenado» en relación con el resto de los elementos, podemos eliminarlo completamente del montón.
Ahora, la buena noticia es que tenemos un nodo menos en nuestro montón para ordenar! ¿La mala noticia? Nuestro montón ya no es realmente un montón: está violando totalmente su regla de ordenación del montón, ya que no es un montón máximo. Fíjate en que 1 es el nodo raíz, pero definitivamente no es más grande que sus dos nodos hijos, 14 y 7. Así que tendremos que moverlo hacia abajo a su lugar correcto en el árbol.
¡Colonicemos este árbol y hagamos un montón máximo de nuevo!
¡Increíble! En la ilustración anterior, podemos ver que primero intercambiamos 1 y 14, y luego intercambiamos 1 y 8. Ahora, volvemos a tener un montón máximo adecuado. Podemos repetir los mismos pasos que hicimos al ordenar el elemento 19:
→ Primero intercambiaremos el primer y el último nodo.
→ A continuación, vamos a heapificar el árbol hasta que vuelva a ser un max heap adecuado.
Hagamos eso con nuestro nuevo nodo raíz, el elemento 14. Estos son los dos pasos siguientes:
¡Rad! Intercambiamos el primer y el último nodo, y luego eliminamos el último nodo, 14, ya que estaba en su posición ordenada. Lo único que teníamos que hacer a continuación era mover el nodo raíz a su posición correcta, y heapificar el elemento 3 hasta que volviéramos a un estado de heap máximo.
Continuaríamos haciendo esto tres veces más. Finalmente, nos quedaría sólo 1, el último nodo del montón. En este punto, el algoritmo de ordenación del montón habría terminado, y sabríamos que 1 sería el primer elemento del array, y sabríamos que el array estaba finalmente ordenado.
Aquí tienes una gran visualización de todo el proceso que acabamos de recorrer. Observa cómo, con cada ordenación iterativa, el elemento más grande sin ordenar acaba en su lugar correcto en el montón, y luego en el array.
Ordenación en montón: ¿para qué sirve?
Cuando leí por primera vez sobre la ordenación en montón, algo del algoritmo me pareció extrañamente familiar. Sólo después de ilustrar la ordenación en montón me di cuenta de dónde provenía mi sensación de déjà vu: ¡la ordenación en montón era casi exactamente igual a la ordenación por selección! Puede que recuerdes que la ordenación por selección es un algoritmo de ordenación que ordena una lista de elementos no ordenados iterando a través de una lista de elementos, encontrando el más pequeño y colocándolo en una lista ordenada. Continúa la ordenación encontrando el elemento más pequeño sin ordenar, y añadiéndolo a la lista ordenada.
¿No suena eso muy parecido a la ordenación en montón, pero al revés?
Resulta que la ordenación en montón se parece mucho a la ordenación por selección en su lógica: ambos algoritmos encuentran el elemento más pequeño o el más grande, lo «seleccionan» y lo colocan en su lugar correcto en la lista ordenada.
Sin embargo, por muy parecidos que sean, la ordenación en montón es mucho mejor que la ordenación por selección en un aspecto enorme: ¡su rendimiento! La ordenación en pila es básicamente una versión súper mejorada de la ordenación por selección. Sí, encuentra el elemento más grande de una colección no ordenada y lo ordena al final de la lista, pero lo hace mucho más rápido que la ordenación por selección.
Bueno, echemos un vistazo al código. Hay varias implementaciones de la ordenación en pila, y el código de abajo es una adaptación de la implementación de la ordenación en pila en JavaScript de Rosetta Code. Recordarás que la ordenación de montón tiene dos partes importantes: buildMaxHeap y heapify. Podemos verlas en acción en la versión de heapSort a continuación.
La función buildMaxHeap hace el trabajo de crear realmente el montón máximo. Observa que incluso esta función llama a heapify, que hace el trabajo de mover un elemento a la vez hacia abajo a su ubicación correcta en el montón.
La función heapify es bastante importante, así que vamos a ver eso. Fíjate en que se basa en los algoritmos para determinar el hijo izquierdo y derecho de un nodo, de los que hablamos la semana pasada cuando aprendimos por primera vez sobre los heaps.
Y por último, pero no por ello menos importante, la función swap, que ya hemos visto antes en otros algoritmos de ordenación, pero que merece la pena ver rápidamente para recordar lo que hace:
Bien, ahora que tenemos un poco de contexto sobre cómo estas funciones interactúan y se invocan unas a otras, volvamos a nuestra pregunta original de cómo y por qué la ordenación por montón es mucho más eficiente que la ordenación por selección. Si miramos en profundidad el código, nos daremos cuenta de dos cosas: en primer lugar, debemos construir el montón máximo una vez, pasándole todos los elementos del array; en segundo lugar, tenemos que acumular todos los elementos del montón una y otra vez, con la excepción del primer elemento del nodo raíz.
Estas dos observaciones son en realidad la clave para saber cómo y por qué la ordenación en montón es tan rápida. Llamar a buildMaxHeap requiere un tiempo O(n), ya que cada elemento debe ser añadido al montón, y una mayor cantidad de elementos significa un montón más grande. Sin embargo, recuerda que estamos tratando con un árbol binario, y los árboles binarios son logarítmicos por naturaleza. Así que, aunque tengamos que llamar a heapify una y otra vez, invocar esta función es en realidad bastante rápido, ya que se ejecutará en tiempo logarítmico, o O(log n).
¡La combinación de estas dos complejidades de tiempo es algo que ya hemos visto antes! La ordenación en montón se ejecuta en tiempo lineal, o en notación Big O, O(n log n). Así que, aunque la ordenación por montón se parece mucho a la ordenación por selección, ¡es mucho más rápida! La ordenación por selección se ejecuta en tiempo cuadrático, o O(n²), lo que es mucho menos eficiente que el tiempo linealítmico.
Veamos rápidamente las otras formas en que la ordenación en montón se compara con otros algoritmos de ordenación.
La ordenación en montón transforma el array que se le pasa mientras ordena; a diferencia de algunos algoritmos de ordenación, no crea una copia completamente separada de los datos de entrada. Esto lo convierte en un algoritmo de ordenación in situ. La ordenación en pila tampoco necesita memoria externa, y es un algoritmo de ordenación interno. Se ejecuta de forma iterativa (y por lo tanto no es recursivo), y compara dos elementos a la vez cuando intercambia y llama a la función heapify, lo que lo convierte en un algoritmo de ordenación por comparación.
Sin embargo, debido a la naturaleza de los montones y la función heapify, si hay elementos duplicados, ¡no podemos confiar en que los elementos mantengan su orden! Por lo tanto, la ordenación en montón es inestable; esta es una de las principales diferencias entre la ordenación por fusión y la ordenación en montón, ya que ambas se basan en estructuras de árbol para funcionar de forma eficiente. Sin embargo, la ordenación por fusión gana la batalla de la estabilidad, mientras que la ordenación en montón fracasa en esta categoría.
A pesar de sus diferencias, la ordenación por fusión y la ordenación en montón pueden estar de acuerdo en una cosa: ¡sin árboles binarios, ambas estarían perdidas!
Recursos
Hay algunos apuntes de cursos y conferencias realmente fantásticos sobre la ordenación en montón, así como algunos buenos tutoriales en vídeo. He buscado en Google para que no tengas que hacerlo tú. Aquí hay algunos grandes lugares para empezar si usted está interesado en aprender más acerca de la ordenación en montón.
- Introducción a los Algoritmos: Ordenación en montón, MIT
- Algoritmos: Ordenación en montón, Profesor Ching-Chi Lin
- Ordenación en montón, Creciendo con la Web
- Ordenación en montón en 4 minutos, Michael Sambol
- Ordenación en montón: Max heap, strohtennis
Leave a Reply