El ordenamiento por montículos (Heap Sort) es un algoritmo de comparación eficiente que utiliza las propiedades de un árbol binario completo para organizar elementos. El proceso se divide fnudamentalmente en dos fases: la construcción inicial del montículo a partir de una lista desordenada y la extracción sucesiva del elemento raíz para obtener la secuencia ordenada.

Montículo Máximo para Orden Ascendente

Para ordenar una colección de forma ascendente, se utiliza un Max-Heap. En esta estructura, el valor de cada nodo padre es mayor o igual que el de sus hijos, garantizando que el elemento más grande siempre se encuentre en la raíz.

public class HeapSortAscendente {
    public static void main(String[] args) {
        int[] valores = {4, 6, 8, 5, 9};
        ejecutarOrdenamiento(valores);
        
        for (int n : valores) {
            System.out.print(n + " ");
        }
    }

    public static void ejecutarOrdenamiento(int[] arreglo) {
        int tamano = arreglo.length;

        // Fase 1: Transformar el arreglo en un Max-Heap
        // Se comienza desde el último nodo que no es hoja
        for (int i = tamano / 2 - 1; i >= 0; i--) {
            reajustarMax(arreglo, tamano, i);
        }

        // Fase 2: Extraer elementos del montículo uno por uno
        for (int j = tamano - 1; j > 0; j--) {
            // Movemos la raíz actual (el máximo) al final del arreglo
            permutar(arreglo, 0, j);
            // Reajustamos el montículo en el área reducida
            reajustarMax(arreglo, j, 0);
        }
    }

    private static void reajustarMax(int[] datos, int limite, int indiceRaiz) {
        int mayor = indiceRaiz;
        int hijoIzquierdo = 2 * indiceRaiz + 1;
        int hijoDerecho = 2 * indiceRaiz + 2;

        // Comprobar si el hijo izquierdo es mayor que la raíz
        if (hijoIzquierdo < limite && datos[hijoIzquierdo] > datos[mayor]) {
            mayor = hijoIzquierdo;
        }

        // Comprobar si el hijo derecho es mayor que el máximo actual
        if (hijoDerecho < limite && datos[hijoDerecho] > datos[mayor]) {
            mayor = hijoDerecho;
        }

        // Si el mayor no es la raíz, intercambiar y continuar reajustando
        if (mayor != indiceRaiz) {
            permutar(datos, indiceRaiz, mayor);
            reajustarMax(datos, limite, mayor);
        }
    }

    private static void permutar(int[] arr, int a, int b) {
        int temporal = arr[a];
        arr[a] = arr[b];
        arr[b] = temporal;
    }
}

Montículo Mínimo para Orden Descendente

Cuando el objetivo es obtener una secuencia en orden descendente, la estructura ideal es el Min-Heap. Aquí, el nodo raíz contiene el valor mínimo de la estructura, el cual se desplaza hacia el final del arreglo en cada iteración.

public class HeapSortDescendente {
    public static void main(String[] args) {
        int[] coleccion = {4, 6, 8, 5, 9};
        ordenarDesc(coleccion);
        
        for (int num : coleccion) {
            System.out.print(num + " ");
        }
    }

    public static void ordenarDesc(int[] lista) {
        int n = lista.length;

        // Construcción del Min-Heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            reajustarMin(lista, n, i);
        }

        // Extracción y reordenamiento
        for (int k = n - 1; k > 0; k--) {
            intercambiar(lista, 0, k);
            reajustarMin(lista, k, 0);
        }
    }

    private static void reajustarMin(int[] arr, int n, int i) {
        int menor = i;
        int izq = 2 * i + 1;
        int der = 2 * i + 2;

        if (izq < n && arr[izq] < arr[menor]) {
            menor = izq;
        }

        if (der < n && arr[der] < arr[menor]) {
            menor = der;
        }

        if (menor != i) {
            intercambiar(arr, i, menor);
            reajustarMin(arr, n, menor);
        }
    }

    private static void intercambiar(int[] arr, int x, int y) {
        int aux = arr[x];
        arr[x] = arr[y];
        arr[y] = aux;
    }
}

La complejidad temporal de este algoritmo es de O(n log n) en todos los casos (mejor, promedio y peor), lo que lo hace muy consistente. Además, es un algoritmo de ordenamiento in-place, ya que solo requiere una cantidad constante de espacio de memoria adicional.