Ordenamiento por montículos
El ordenamiento por montículos (heapsort) es un ordenamiento por selección con una forma mejor de encontrar el mayor valor. Guarda los valores sin ordenar en un montículo, un árbol almacenado dentro de la propia lista, donde el mayor valor siempre está en la cima. Sacarlo y reparar el montículo lleva unos log n pasos en lugar de un recorrido completo.
Un árbol dentro de una lista
Un montículo binario es un árbol que no necesita punteros. La posición 0 es la raíz, y los hijos de la posición i son las posiciones 2i + 1 y 2i + 2; así, las posiciones 1 y 2 son los hijos de la raíz, las posiciones 3 a 6 el siguiente nivel, y así sucesivamente. Todos los niveles están llenos salvo el último, que se llena desde la izquierda. En un montículo máximo cada padre es al menos tan grande como sus hijos, así que el mayor valor siempre está en la raíz.
Hundir un valor
Una sola operación hace todo el trabajo. Para hundir un valor, compáralo con sus hijos. Si el hijo mayor es mayor que el valor, se intercambian, y el valor se compara con sus nuevos hijos. Se detiene cuando ningún hijo es mayor o cuando llega al fondo. Como el árbol solo tiene unos log₂ n niveles, un hundimiento hace como mucho unas 2 log₂ n comparaciones.
Construir el montículo y luego ordenar
Para construir el montículo, hunde cada padre, desde el último hasta la raíz. Cada subárbol ya es un montículo antes de que su padre se hunda en él. Después, ordena: intercambia la raíz, el mayor valor, con el último valor del montículo. Ese valor ya está en su lugar definitivo. El montículo es uno más corto, y el valor que ha llegado a la raíz se hunde para repararlo. Repite hasta que quede un solo valor.
Un ejemplo
Toma 5, 1, 4, 2, 8. Al construir el montículo, 1 se hunde bajo 8 y luego 5 se hunde bajo 8, lo que da 8, 5, 4, 2, 1. Ahora 8 pasa al final; 1 llega a la raíz y se hunde por debajo de 5 y 2: 5, 2, 4, 1 | 8. Luego 5 pasa al final y 1 se hunde por debajo de 4: 4, 2, 1 | 5, 8. Dos rondas más terminan la lista: 1, 2, 4, 5, 8, tras 12 comparaciones y 10 intercambios.
Ventajas e inconvenientes
El ordenamiento por montículos lleva un tiempo proporcional a n log n incluso en el peor caso, y no necesita memoria adicional. Quicksort puede ralentizarse hasta n² y el ordenamiento por mezcla necesita un búfer tan largo como la lista, así que el ordenamiento por montículos es la alternativa segura: introsort, que usa la biblioteca estándar de C++, recurre a él cuando las particiones de quicksort salen mal. En ordenadores reales suele ser más lento que ambos, porque salta entre posiciones lejanas de la lista, y no es estable. J. W. J. Williams publicó el ordenamiento por montículos, junto con el montículo binario, en 1964.
Explóralo
Abre la aplicación y pulsa Paso. El árbol sobre las barras muestra el montículo: el valor que se hunde tiene su propio color, el hijo con el que se compara está resaltado, y cada intercambio se ve tanto en el árbol como en las barras. Cuando el montículo esté construido, observa cómo la raíz pasa al final, se vuelve verde y sale del árbol.
Preguntas frecuentes
¿Cuál es la complejidad temporal del ordenamiento por montículos?
O(n log n) en el mejor caso, el caso medio y el peor caso. Construir el montículo lleva O(n), y cada una de las n − 1 extracciones lleva O(log n). Ordena in situ con O(1) de memoria adicional.
¿Qué diferencia hay entre el ordenamiento por montículos y el ordenamiento por selección?
Los dos toman una y otra vez el mayor (o el menor) valor restante. El ordenamiento por selección lo encuentra recorriendo toda la parte sin ordenar, n comparaciones cada vez. El ordenamiento por montículos guarda la parte sin ordenar en un montículo, donde el mayor valor ya está en la cima, y reparar el montículo solo cuesta unas log n comparaciones.
¿Para qué se usa un montículo además de para ordenar?
Para colas de prioridad: un montículo da al instante el mayor (o el menor) elemento y permite añadir o quitar elementos en unos log n pasos. Los planificadores, el algoritmo de caminos más cortos de Dijkstra y las simulaciones de eventos usan uno.
¿Es estable el ordenamiento por montículos?
No. Al intercambiar la raíz con el final, los valores se mueven a grandes distancias, así que valores iguales pueden cambiar su orden.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba el ordenamiento por montículos