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:
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];
}
}