Ordenamiento de montón básico
1. Concepto e introducción
El ordenamiento de montón (Heapsort) es un algoritmo de ordenamiento diseñado utilizando la estructura de datos de montón.
Un montón es una estructura aproximadamente de árbol binario completo y, al mismo tiempo, satisface la propiedad de acumulación: el valor clave o índice de un nodo hijo es siempre menor (o mayor) que el de su nodo padre.
2. Instrucciones de aplicación
El proceso anterior de construcción del montón consistía en llamar al método insert para cada dato y usar shift up para insertarlos uno a uno en el montón; la complejidad temporal de este algoritmo esO(nlogn)el proceso de construcción de ordenamiento de montón presentado en esta subsección se llamaHeapifyy la complejidad temporal del algoritmo esO(n)。
3. Diagrama del proceso
El árbol binario completo tiene una propiedad importante: el índice del primer nodo no hoja esn/2el valor de índice obtenido tomando la parte entera, dondenes el número de elementos (suponiendo que los índices del arreglo comienzan en 1).

La posición con índice 5 es el primer nodo no hoja; comenzamos desde allí y avanzamos uno a uno hacia adelante, tomando cada elemento como nodo raíz y realizando la operación shift down para cumplir la propiedad del montón máximo.
Después de realizar la operación shift down en la posición con índice 5, el 22 y el 62 intercambian posiciones.

Realizar la operación shift down sobre el elemento en el índice 4

Realizar la operación shift down sobre el elemento en el índice 3

Realizar la operación shift down sobre el elemento en el índice 2

Finalmente, se realiza la operación shift down sobre el nodo raíz y todo el proceso de ordenamiento de montón está completo.

4. Código de ejemplo en Java
Descarga del paquete de código fuente:Download
Código del archivo src/ejemplo/heap/Heapify.java:
import ejemplo.sort.SortTestHelper;
/**
* Ordenamiento de montón usando heapify
*/
public class Heapify<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructor, crea un montón máximo a partir de un arreglo dado
// El proceso de construcción del montón tiene una complejidad temporal de O(n)
public Heapify(T arr[]){
int n = arr.length;
data = (T[])new Comparable[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )
data[i+1] = arr[i];
count = n;
// Comenzar desde el primer elemento que no es un nodo hoja
for( int i = count/2 ; i >= 1 ; i -- )
shiftDown(i);
}
// Devuelve el número de elementos en el montón
public int size(){
return count;
}
// Devuelve un valor booleano que indica si el montón está vacío
public boolean isEmpty(){
return count == 0;
}
// Inserta un nuevo elemento item en el montón máximo
public void insert(T item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
}
// Extrae el elemento superior del montón máximo, es decir, los datos máximos almacenados en el montón
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Obtiene el elemento superior del montón máximo
public T getMax(){
assert( count > 0 );
return data[1];
}
// Intercambia dos elementos con índices i y j en el montón
private void swap(int i, int j){
T t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* Funciones auxiliares centrales del montón máximo
//********************
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
swap(k, k/2);
k /= 2;
}
}
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // En este bucle, data[k] y data[j] intercambian posiciones
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] es el máximo entre data[2*k] y data[2*k+1]
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
}
// Probar heapify
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
Heapify<Integer> heapify = new Heapify<Integer>(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 ++ ){
arr[i] = heapify.extractMax();
System.out.print(arr[i] + " ");
}
// Asegurar que el arreglo arr esté ordenado de mayor a menor
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}