Heapsort
Organiza la lista como un montículo, un árbol donde cada padre es mayor que sus hijos. Luego mueve el mayor valor al final, una y otra vez.
- mejor caso Ω(n log n)
- caso medio Θ(n log n)
- peor caso O(n log n)
- espacio O(1)
- no estable
- sin memoria extra
¿Qué significan estos términos?
- Mejor caso: cómo crece el tiempo con el tamaño n de la lista cuando la entrada es la más fácil para este algoritmo.
- Caso medio: cómo suele crecer el tiempo con n. Con n², el doble de valores tarda unas cuatro veces más; n log n crece mucho más despacio.
- Peor caso: el crecimiento con la entrada más difícil. Útil cuando la velocidad nunca debe caer.
- Espacio: cuánta memoria extra hace falta además de la lista. 1 son unas pocas variables; n, una copia de la lista.
- Estable: dos valores iguales conservan su orden original. Importa al ordenar registros por un solo campo.
- Sin memoria extra: ordena dentro de la propia lista, sin una segunda lista.
- comparando
- moviendo
- en su lugar final
Pulsa reproducir: las líneas muestran cómo crece el coste
Pulsa reproducir o avanza paso a paso.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige una lista invertida. Construir el montículo casi no requiere intercambios; luego cada ronda lleva el mayor valor al final.
Cómo funciona
El montículo se guarda dentro de la propia lista: el valor en la posición i tiene sus hijos en las posiciones 2i+1 y 2i+2, y el mayor valor está siempre al principio. Se intercambia con el último valor, el montículo se reduce en uno y se repara. La parte ordenada crece desde la derecha.
Cuándo es una buena opción
Cuando necesitas una velocidad que siga siendo buena incluso en el peor caso y sin memoria extra, por ejemplo en dispositivos pequeños. De media es más lento que quicksort, así que suele usarse como red de seguridad.