Una de las aplicaciones de los Heaps o Montículos es el
algoritmo HeapSort, el cual es uno de tantos que permite ordenar
un conjunto "S" de datos en tiempo “linearítmico“ O(n logn). No es un algoritmo
estable, es decir, no garantiza que los elementos tengan el mismo orden relativo
después de la ordenación, pero a diferencia de otros algoritmos como Quicksort siempre garantiza O(n logn) como mejor, promedio o peor caso.
Una vez que se entiende la estructura de datos Heap el algoritmo es bastante sencillo y se basa en los siguientes pasos:
- Construir un MaxHeap o MinHeap a partir de un arreglo.
- Inicializar un ciclo desde I=heap.Length – 1 hasta I > 1 e Ir eliminando el tope (intercambiándolo con el último elemento I). Luego se verifica desde el primer nodo que se mantenga la propiedad del montículo (El mayor o menor elemento esté en el tope) esta operación generalmente se conoce como Heapify.
La explicación de eliminar del tope junto con Heapify puedes leerlas en mi post sobre Heaps o montículos, donde las explico con imágenes para que se entienda un poco mejor. Cabe destacar que para ordenar de manera creciente se utiliza un MaxHeap y para ordenar de manera decreciente un MinHeap. De igual manera, vale mencionar que la mayoría de las implementaciones de este algoritmo son en sitio, es decir, se modifica directamente el arreglo que se quiere ordenar.
