El algoritmo de ordenación Montículo “Heap”, es un algoritmo que trabaja de forma similar al de Selección, divide el vector en una región ordenada y no ordenada, su mejora radica en el uso de una estructura en pila (árbol binario, ascendente o descendente) en lugar de una búsqueda en tiempo lineal para encontrar el máximo. Fue desarrollado por J. J. Williams en 1.964 y su complejidad es O(n log n).
Rendimiento – Complejidad | |||
Mejor caso Ω |
Peor caso O |
Media Θ |
Espacio |
(n log n) | (n log n) | (n log n) | O(1) |
El árbol se llena de izquierda a derecha, está perfectamente balanceado y las hojas del ultimo nivel están todas en las posiciones en el extremo izquierdo.
Rendimiento.
Estadística individual realizada con el mismo equipo y condiciones del resumen de estadísticas de ordenación.