Algoritmo Heap Sort

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:

1. Construir un MaxHeap o MinHeap a partir de un arreglo.
2. 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.

Paso 1
Para construir el heap hay que recorrer el arreglo, recordemos que un montículo se basa un arreglo, desde (arreglo.Length / 2) hasta > 1. Se hace desde abajo hacia arriba porque a partir de (arreglo.Length) / 2 + 1 todos los nodos son hijos y en Heapify se deben verificar los nodos padres contra los hijos e ir intercambiando según sea el caso (con el mayor o el menor de los hijos) para mantener la propiedad del montículo. En Pseudocódigo sería algo como:

void BuildHeap(int[] array)
{
    for (int i = array.Length / 2; i <= 0; i--)
    {
        //Hacer cumplir la propiedad del heap dependiendo
        //si es un MaxHeap o un MinHeap
        Heapify(array, i, array.Length);
    }
}

Paso 2
Dentro de un ciclo vamos intercambiando el primer con el último elemento no ordenado y luego llamamos a Heapify para mantener la propiedad del Heap en la parte no ordenada del arreglo.

void Sort(int[] array)
{
    BuildHeap(array);

    for (int length = array.Length - 1; length > 1; length--)
    {
        Swap(array, 0, length);
        Heapify(array, 0, length);
    }
}

Implementación en Golang
Dejo esta implementación en Go, como modo de practica, ya que estoy aprendiendo este lenguaje y me está gustando bastante, están todas las funciones mencionadas en el artículo, junto con un pequeño ejemplo que imprime un array antes y después de ser ordenado:

<EOF>

También puedes encontrar una implementación en C# de este y otros algoritmos, con algunos Test Unitarios, en mi repositorio de github para algoritmos. Como nota interesante, Heap Sort es el método de ordenación utilizado en el kernel de Linux.

Referencias
https://en.wikipedia.org/wiki/Heapsort

https://en.wikipedia.org/wiki/Sorting_algorithm#Stability