HEAPSORT

Para poder realizar un ordenamiento mediante HeapSort, es necesario primero generar primero la estructura Heap ó montículo. Seguramente, anteriores veces has manejado estas estructuras o al menos has escuchado hablar de ellas.

Un Heap es un árbol binario completo, que permite implementar una cola con prioridades, y donde los elementos se almacenan cumpliendo la propiedad de que la llave (o valor) de un nodo siempre es mayor que la llave de cualquiera de sus hijos. Por lo tanto, la raíz del árbol, en un Heap, siempre es el elemento mayor de la estructura.

Un Heap puede ser almacenado en un vector sin ocasionar inconvenientes en el manejo de la estructura, evitando el uso de punteros. El Heap se almacena en un arreglo A[1..n], y utiliza una variable que indica cuantos elementos tiene.

El algoritmo HeapSort, consiste en remover el mayor elemento que es siempre la raíz del Heap, una vez seleccionado el máximo, lo intercambiamos con el último elemento del vector, decrementamos la cantidad de elementos del Heap y nos encargamos de reacomodarlo para que vuelva a ser un Heap.

Ejemplo:

Este es un heap y su representación en forma de vector es:

Ahora, el algoritmo de Heapsort para otro heap es:

En términos sencillos, el algoritmo de Heapsort toma en cuenta los siguientes pasos:

Entrada: Un arreglo A[1...n] donde cada A[i] es un nodo del heap.

Salida: La secuencia ordenada de los A[i]

for(i = n hasta 2)

{

Sacar (ó Imprimir en la secuencia) a A[1];

A[1] = A[i];

Borrar a A[i];

Reacomodar Heap(1, i-1);

}

El ordenamiento por heap sort forma parte de los algoritmos de ordenamiento cuyas complejidades temporales son O(n log n), aún para el peor caso, a diferencia de muchos otros algoritmos de ordenamiento como los que ya hemos visto, donde para el peor caso se tiene un orden de O(n^2). Heap sort alcanza esta complejidad temporal de O(n log n) debido esencialmente a que utiliza una estructura de datos de modo que cada operación de salida requiere a lo sumo log i pasos, donde i es el número de elementos restantes. Nótese que este inteligente diseño de estructura de datos es fundamental para el ordenamiento heap sort.