Shift up del montón

Esta sección introduce cómo agregar un elemento a un montón máximo, llamadoshift up。

Supongamos que agregamos un nuevo elemento 52 al siguiente montón máximo, colocándolo en la última posición del array. Como 52 es mayor que el nodo padre 16, en este momento no cumple con la definición del montón, por lo que es necesario ajustarlo.

Primero, se intercambian las posiciones de los valores en el array con índices 5 y 11, es decir, se intercambian 52 y 16.

En este momento, 52 sigue siendo mayor que el valor 41 del nodo padre con índice 2, por lo que necesitamos moverlo más.

Ahora comparamos 52 y 62. 52 ya es más pequeño que el nodo padre, no necesita subir más y cumple con la definición del montón máximo. A este proceso lo llamamos shift up del montón máximo.

Código de ejemplo en Java

Descargar paquete de código fuente:Download

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

package ejemplo.heap;

/**
* Añadir un elemento al montón
 */
public class HeapShiftUp<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Constructor, construye un montón vacío que puede contener capacity elementos
    public HeapShiftUp(int capacity){
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // Devuelve el número de elementos del 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);
    }
    // Intercambia los dos elementos del montón con índices i y j
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Funciones auxiliares principales 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;
        }
    }

    // Probar HeapShiftUp
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // Número de elementos del montón
        int M = 100; // El rango de valores de los elementos del montón es [0, M)
        for( int i = 0 ; i < N ; i ++ )
            heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(heapShiftUp.size());

    }
}
Otras extensiones