- Hundiéndose
- Comparadas
- Intercambiadas
- En su sitio
Ordenamiento por montículos
El ordenamiento por montículos (heapsort) lee la lista como un árbol binario y la reorganiza en un montículo máximo, donde cada padre es al menos tan grande como sus hijos. Así el mayor valor queda en la cima. Intercámbialo con el final, donde se queda, repara el montículo y repite. La aplicación dibuja el montículo como un árbol sobre las barras, para que sigas cada valor mientras se hunde. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. El árbol sobre las barras muestra los mismos valores como un montículo. Los recuadros cuentan comparaciones, intercambios y valores extraídos del montículo. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Elige cuántas barras hay y cómo empiezan: aleatorias, casi ordenadas, invertidas o con pocos valores distintos. O escribe tus propios números.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
- Observa el árbol: primero cada padre se hunde hasta que el montículo está construido; después la raíz se intercambia con el final y el montículo se acorta en uno.
Cómo funciona el ordenamiento por montículos
Lee la lista como un árbol: el valor de la posición i tiene sus hijos en las posiciones 2i + 1 y 2i + 2. Construye un montículo máximo hundiendo cada padre, empezando por el último: mientras un valor sea menor que su hijo mayor, los dos se intercambian. Cuando la raíz tiene el mayor valor, intercámbialo con el último valor del montículo. Ese valor ya es definitivo, el montículo es uno más corto y la nueva raíz se hunde para que vuelva a ser un montículo. Repite hasta que el montículo esté vacío.
Siempre n log n, in situ
El árbol tiene unos log₂ n niveles, así que cada hundimiento hace como mucho unas 2 log₂ n comparaciones, y construir el montículo, menos de 2n. Eso da al ordenamiento por montículos un peor caso de unas 2n log₂ n comparaciones, sin búfer: para 40 valores, como mucho 352. A diferencia de quicksort, no tiene entradas malas, y a diferencia del ordenamiento por mezcla, no necesita memoria adicional. En la práctica suele ser más lento que ambos, porque salta de un lado a otro de la lista, y no es estable.
Preguntas frecuentes
¿Cómo funciona el ordenamiento por montículos?
Convierte la lista en un montículo máximo, un árbol guardado en la lista donde cada padre es al menos tan grande como sus hijos. Luego, una y otra vez, intercambia el mayor valor, en la raíz, con el final del montículo y hunde la nueva raíz para repararlo.
¿Qué es un montículo?
Un árbol binario completo guardado en una lista sin punteros: los hijos de la posición i son las posiciones 2i + 1 y 2i + 2. 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, en la posición 0.
¿Por qué construir el montículo es rápido?
La mayoría de los valores están cerca de la base del árbol y solo pueden hundirse uno o dos niveles. Sumando el trabajo de todos los niveles salen menos de 2n comparaciones para toda la construcción, no n log n.
¿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 de orden.
¿Se envían mis números a algún sitio?
No. La ordenación se ejecuta en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor