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

martes, 20 de octubre de 2009

Implementacion de Merge Sort en Java



private int[] mergeSortImpl(int[] array) {
// Caso base. Un arreglo de cero o un elemento ya esta ordenado,
// asi que lo regresamos.
if (array.length <= 1) {
return array;
}
int puntoMedio = array.length / 2;
// Creamos subarreglo izquierdo
int[] izquierdo = new int[puntoMedio];
for (int i = 0; i < puntoMedio; i++) {
izquierdo[i] = array[i];
}
// Creamos el subarreglo derecho
int[] derecho = new int[array.length - puntoMedio];
for (int i = 0; i < array.length - puntoMedio; i++) {
derecho[i] = array[puntoMedio + i];
}
// Ordenamos las dos mitades recursivamente
int[] izquierdoOrdenado = mergeSortImpl(izquierdo);
int[] derechoOrdenado = mergeSortImpl(derecho);
//Mezclamos la solucion---
// El indice i es para recorrer el subarreglo izquierdo
int i = 0;
// El indice j es para recorrer el subarreglo derecho
int j = 0;
// En 'resultado' guardamos el resultado de la mezcla de los dos
// subarreglos
int[] resultado = new int[izquierdoOrdenado.length + derechoOrdenado.length];
/**
* Terminamos de mezclar cuando i + j ya recorrieron todos los elementos
* de los dos subarreglos
*/
while (i + j < izquierdoOrdenado.length + derechoOrdenado.length) {
// a) Si i ya llego al ultimo elemento del subarreglo izquierdo
// copiamos el valor del siguiente elemento del subarreglo
// derecho e incrementamos el indice j para, en el siguiente,
// ciclo copiar el elemento de subarreglo derecho que sigue
if (i == izquierdoOrdenado.length) {
resultado[i + j] = derechoOrdenado[j];
j++;
continue;
}
// Lo mismo que a) pero para el subarreglo derecho
if (j == derechoOrdenado.length) {
resultado[i + j] = izquierdoOrdenado[i];
i++;
continue;
}
int elementoIzquierdo = izquierdoOrdenado[i];
int elementoDerecho = derechoOrdenado[j];
// Comparamos cual de los elementos que siguen es menor y ese
// lo copiamos en resultado
if (elementoIzquierdo <= elementoDerecho) {
resultado[i + j] = elementoIzquierdo;
i++;
} else {
resultado[i + j] = elementoDerecho;
j++;
}
}
return resultado;
}