Heapsort

Heapsort

El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional.

Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, recoloca en el nodo raíz o cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad heap del árbol. Pero, a continuación realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente "hunde" el nodo en el árbol restaurando la propiedad montículo del arbol y dejándo paso a la siguiente extracción del nodo raíz.

Algoritmo.

1. Se construye el montículo inicial a partir del arreglo original.

2. Se intercambia la raíz con el último elemento del montículo.

3. El último elemento queda ordenado.

4. El último elemento se saca del montículo, no del arreglo.

5. Se restaura el montículo haciendo que el primer elemento baje a la posición que le corresponde, si sus hijos son menores.

6. La raíz vuelve a ser el mayor del montículo.

7. Se repite el paso 2 hasta que quede un solo elemento en el montículo.

Tiempo de ejecución

•Este método garantiza que el tiempo de ejecución siempre es de: O(n log n)

•El Heapsort está basado en el uso de un tipo especial de árbol binario. La estructura de ramificación del árbol conserva el número de comparaciones necesarias en n log n.

Ventajas

Su desempeño es en promedio tan bueno como el Quicksort y se comporta mejor que este último en los peores casos.

Desventajas

Aunque el Heapsort tiene un mejor desempeño general que cualquier otro método presentado de clasificación interna, es bastante complejo de programar.

Ejemplos de implementación en C++

Ordenar

...