jueves, 22 de octubre de 2009

Implementacion de un Heap de números enteros en Java.


/**
* Clase para implementar un heap de numeros enteros.
*/
public class Heap {

/**
* Aqui guardamos el heap.
*/
private int[] heap;
/**
* Lleva la cuenta del numero de elementos en el heap.
*/
private int numeroElementos = 0;

/**
* Recibe como argumento un arreglo del que extraera sus valores y los
* copiara uno a uno en el heap usando el metodo inserta.
* @param array El arreglo que introduciremos al heap.
*/
public Heap(final int[] array) {
heap = new int[array.length];
for (int i = 0; i < array.length; i++) {
int j = array[i];
inserta(j);
}
}

/**
* Hace una copia del heap y lo devuelve.
* @return Una copia de los valores del heap.
*/
public final int[] getValue() {
return heap.clone();
}

/**
* Inserta un entero en el heap en la ultima posicion disponible y reordena
* el heap para conservar la propiedad de orden se siga cumpliendo.
* @param elemento El elemento a ordenar.
*/
public final void inserta(int elemento) {
if (numeroElementos == heap.length) {
throw new IllegalStateException("Error, el heap esta lleno. " +
"Elemento a insertar: " + elemento + " Heap size: " +
numeroElementos);
}
// Cuando no hay elementos insertamos el elemento en la
// primera posicion del arreglo que es la raiz del heap
if (numeroElementos == 0) {
heap[0] = elemento;
numeroElementos++;
return;
}
boolean esPadreMayor = false;
// indiceHijo es el ultimo lugar del heap. Aqui es donde empezamos
// a buscar la posicion del elemento a insertar. Posteriormente calcula
// mos la posicion del padre de este nodo.
int indiceHijo = numeroElementos;
// Aqui guardamos el indice del nodo padra del nodo hijo.
int indicePadre = 0;
// Calculamos el indice del nodo padre.
if (indiceHijo % 2 == 0) {
indicePadre = (int) (Math.ceil(indiceHijo / 2)) - 1;
} else {
indicePadre = (int) (Math.ceil(indiceHijo / 2));
}
int valorPadre = heap[indicePadre];
while (true) {
// Terminamos cuando el padre que estamos analizando es mayor
// que el valor del hijo actual. O cuando ya llegamos a la raiz
// del arbol, que es cuando el indiceHijo == 0
if (esPadreMayor || indiceHijo == 0) {
break;
}
// Si encontramos que el valor del padre del nodo actual
// es mayor que el valor del elemenot que estamos insertando
// guardamos el valor del elemento en el nodo actual (indiceHijo)
// y marcamos la variable esPadreMayor = true para en el siguiente
// ciclo finalizar.
if (valorPadre > elemento) {
heap[indiceHijo] = elemento;
esPadreMayor = true;
continue;
}
// Sino se cumple ninguna de las condiciones anteriores, intercam
// biamos el valor del nodo padre con el hijo y actualizamos
// los indices. 'indiceHijo = indicePadre' para en la siguiente
// iteracion repetir el mismo proceso.
heap[indicePadre] = elemento;
heap[indiceHijo] = valorPadre;
indiceHijo = indicePadre;
// Una vez calculado el nuevo indiceHijo, calculamos el nuevo
// indicePadre.
if (indiceHijo % 2 == 0) {
indicePadre = (int) (Math.ceil(indiceHijo / 2)) - 1;
} else {
indicePadre = (int) (Math.ceil(indiceHijo / 2));
}
if (indicePadre >= 0) {
valorPadre = heap[indicePadre];
}
}
numeroElementos++;
}

/**
* Obtiene el valor de la raiz del heap y reordena los elementos para
* mantener la propiedad del heap.
* @return En cada llamada obtiene el valor maximo del heap, eliminando
* dicho elemento y reordenando el heap para que en la siguiente
* llamada obtenga el valor maximo del heap restante.
*/
public final int quitaRaiz() {
if (numeroElementos == 0) {
throw new IllegalStateException("Error, el heap esta vacio");
}
int resultado = heap[0];
heap[0] = heap[--numeroElementos];
int indiceNodo = 0;
int indiceHijoMayor = 0;
while (true) {
int indiceHijoIzquierdo = indiceNodo * 2 + 1;
int indiceHijoDerecho = indiceNodo * 2 + 2;
if (indiceHijoIzquierdo >= numeroElementos) {
break;
} else {
// Determinar cual de los dos hijos es el mayor
if (indiceHijoDerecho >= numeroElementos) {
indiceHijoMayor = indiceHijoIzquierdo;
} else {
if (heap[indiceHijoIzquierdo] > heap[indiceHijoDerecho]) {
indiceHijoMayor = indiceHijoIzquierdo;
} else {
indiceHijoMayor = indiceHijoDerecho;
}
}
}
/**
* Intercambiar los valores del indiceNodo y el indiceHijoMayor
* si es que el valor del hijo mayor es mayor que el valor del
* nodo actual. En caso que no sea así terminamos.
*/
int valorHijoMayor = heap[indiceHijoMayor];
if (valorHijoMayor > heap[indiceNodo]) {
heap[indiceHijoMayor] = heap[indiceNodo];
heap[indiceNodo] = valorHijoMayor;
// Actualizar el valor del indiceNodo por indiceHijoMayor
indiceNodo = indiceHijoMayor;
} else {
break;
}
}
return resultado;
}
}

No hay comentarios:

Publicar un comentario