Optimización del ordenamiento por montones

En el ordenamiento por montones de la sección anterior, abrimos espacio adicional para construir el montón y ordenarlo. En esta subsección, lo optimizamos utilizando el ordenamiento por montones in situ.

Para un montón máximo, primero se intercambia el dato en la posición inicial con el valor al final del array, de modo que el final del array sea el elemento máximo. Luego se realiza la operación shift down sobre ese elemento para regenerar el montón máximo. Después se intercambia el nuevo número máximo con la penúltima posición de todo el array, de modo que la penúltima posición sea el segundo dato más grande. Este proceso se repite sucesivamente.

Todo el proceso se puede representar con la siguiente figura:

Código de ejemplo en Java

Descarga del paquete de código fuente:Download

Código del archivo src/ejemplo/heap/HeapSort.java:

package ejemplo.heap;

import ejemplo.sort.SortTestHelper;

/**
* Ordenamiento por montones in situ
 */

public class HeapSort<T extends Comparable> {


    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // Nota: nuestro montón está indexado desde 0
        // Empezar desde (índice del último elemento - 1) / 2
        // El índice del último elemento = n-1
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
            shiftDown(arr, n, i);
       
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    // Intercambiar los dos elementos en los índices i y j del montón
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Proceso original de shiftDown
    private static void shiftDown(Comparable[] arr, int n, int k) {

        while (2 * k + 1 < n) {
            // Nodo hijo izquierdo
            int j = 2 * k + 1;
            // El nodo hijo derecho es mayor que el nodo hijo izquierdo
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
                j += 1;
            // Es mayor que ambos nodos hijos
            if (arr[k].compareTo(arr[j]) >= 0) break;
            // Intercambiar el valor del nodo original y el de un nodo hijo
            swap(arr, k, j);
            k = j;
        }
    }

    // Probar HeapSort
    public static void main(String[] args) {

        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        // Extraer gradualmente los datos de heapify usando extractMax
        // El orden de extracción debe ser de mayor a menor
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        // Asegurar que el array arr esté ordenado de mayor a menor
        for (int i = 1; i < N; i++)
            assert arr[i - 1] >= arr[i];
    }
}
Otras extensiones