Shift down del montón
En esta sección se explicará cómo extraer un elemento de un montón máximo, lo que se llama shift down. Solo se puede extraer el elemento de máxima prioridad, es decir, el nodo raíz. Después de extraer el 62 original, a continuación se explica cómo rellenar este montón máximo.

Primer paso, colocamos el último elemento del array en el nodo raíz; en este momento no se cumple la definición de montón máximo.

El proceso de ajuste consiste en mover el nodo raíz 16 hacia abajo paso a paso. 16 es más pequeño que sus nodos hijos. Primero se compara cuál de los hijos 52 y 30 es mayor, y se intercambia con el mayor.

Continuamos comparando los nodos hijos de 16, 28 y 41; 41 es mayor, por lo que 16 y 41 intercambian posiciones.

Continuamos comparando 16 con su nodo hijo 15; 16 es mayor, por lo que no es necesario intercambiar. Finalmente, nuestra operación shift down se completa, manteniendo la propiedad de montón máximo.
Cuatro, código de ejemplo de Java
Descarga del paquete de código fuente:Download
Código del archivo src/ejemplo/heap/HeapShiftDown.java:
/**
* Extraer un elemento del montón máximo
*/
public class HeapShiftDown<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructor, construye un montón vacío, puede contener capacity elementos.
public HeapShiftDown(int capacity){
// Aquí sumar 1 se refiere a la cantidad de elementos que originalmente podía contener; al eliminar la posición 0, solo puede contener capacity elementos.
data = (T[])new Comparable[capacity+1];
count = 0;
this.capacity = capacity;
}
// 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, el dato más grande almacenado 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 los 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;
}
//********************
//* Función auxiliar central 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;
}
}
// Operación shiftDown
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // En esta iteración del bucle, data[k] y data[j] intercambian posiciones.
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] es el valor máximo entre data[2*k] y data[2*k+1].
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
System.out.println(Fin de shiftDown);
}
// Probar HeapShiftDown
public static void main(String[] args) {
HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
// Número de elementos en el montón.
int N = 100;
// Rango de valores de los elementos del montón [0, M)
int M = 100;
for( int i = 0 ; i < N ; i ++ )
heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// Extraer gradualmente los datos del montón máximo utilizando extractMax.
// El orden de extracción debe ser de mayor a menor.
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapShiftDown.extractMax();
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];
}
}