Montículo

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)

Montículo. Algoritmo de ordenación en Java

 

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.

 

 

Rendimiento algoritmo Montículo Heapsort de 10 a 100mil elementos

 

Rendimiento algoritmo Montículo Heapsort de100mil a 1Millón de elementos