Heap Sort [1] tiene complejidades de tiempo O(nlogn) para todos los casos (mejor caso, caso promedio y peor caso).
Déjanos entender la razón por la cual. La altura de un árbol binario completo que contiene n elementos es log(n)
Para heapificar por completo un elemento cuyos subárboles ya tienen un montón máximo, debemos seguir comparando el elemento con sus elementos secundarios izquierdo y derecho y empujarlo hacia abajo hasta que llegue a un punto en el que sus elementos secundarios sean más pequeños que él.
- ¿Cómo funciona el algoritmo de Google Maps?
- ¿Dónde puedo encontrar a alguien dispuesto a enseñarme estructura de datos y algoritmos de forma gratuita o a un costo muy barato?
- ¿Cuál es el problema de partición y cómo lo resolvemos?
- ¿Cuál es el menor número de operaciones necesarias para ordenar una matriz de n objetos arbitrarios?
- ¿Cuál es el mejor algoritmo para realizar la extracción de características para el reconocimiento óptico de caracteres?
En el peor de los casos, tendremos que mover un elemento desde la raíz al nodo hoja haciendo un múltiplo de log(n) comparaciones e intercambios.
Durante la etapa build_max_heap, hacemos eso para n/2 elementos, por lo que la peor complejidad del paso build_heap es n/2*log(n) ~ nlogn .
Durante el paso de clasificación, intercambiamos el elemento raíz con el último elemento y heapificamos el elemento raíz. Para cada elemento, esto requiere de logn peor tiempo porque podríamos tener que llevar el elemento desde la raíz hasta la hoja. Como repetimos esto n veces, el paso nlogn también es nlogn .
Además, dado que los pasos build_max_heap y heap_sort se ejecutan uno tras otro, la complejidad algorítmica no se multiplica y permanece en el orden de nlogn .
También realiza la clasificación en O(1) complejidad del espacio. En comparación con Quick Sort, tiene el peor de los casos ( O(nlogn) ) . La clasificación rápida tiene complejidad O(n^2) para el peor de los casos. Pero en otros casos, Quick Sort es rápido. Introsort es una alternativa al heapsort que combina quicksort y heapsort para conservar las ventajas de ambos: la peor velocidad de heapsort y la velocidad promedio de quicksort.
Notas al pie
[1] Algoritmo de ordenación del montón
