viernes, 7 de octubre de 2011

Ordenamiento por montículos - HeapSort

Hace mucho que no escribo nada sobre algoritmos y eso... bueno, esta vez quiero poner un código de ejemplo para el algoritmo de ordenamiento "HeapSort".
Fig. 1 - Funcionamiento de HeapSort.
El algoritmo HeapSort utiliza una estructura llamada "montículo" que no es otra cosa más que un árbol binario donde cada nodo padre siempre tiene un valor mayor que el de todos sus nodos hijos. Además de ello un montículo debe ser un árbol binario completo. Más información sobre montículos, en la wikipedia.

El algoritmo consiste en insertar todos los elementos del vector en un montículo y aprovechar que de esta forma siempre tendremos el mayor elemento en la raíz. Luego para obtener los elementos ordenados de mayor a menor, solo debemos tomar el valor de la raíz, eliminar la raíz y reordenar el montículo cada vez hasta agotar sus nodos.

Los métodos para insertar en el montículo y para reordenarlo son de orden logarítmico (log(n)) y los recorridos para insertar y eliminar los elementos del monticulo son de orden lineal (n) por lo que la complejidad del HeapSort es de orden n*log(n), igual a otros algoritmos de ordenamiento eficientes como el MergeSort o el QuickSort pero con la ventaja de que HeapSort no utiliza recursividad.

Para la implementación de HeapSort, he representado el montículo con un vector donde si un elemento está en la posición "i" sus hijos estarán en las posiciones "i*2+1" y "i*2+2".

Sin más vamos al código...

/*
	Algoritmo de ordenamiento HeapSort.
	Por: Alguien
	Fecha: Viernes 07 de octubre del 2011
*/
#include <stdio.h>

/*
	Inserta un elemento en el monticulo.
	v  Vector de elementos (monticulo)
	n  Numero de elementos en el vector
	x  Nuevo elemento 
*/
void heap_insert(int *v, int n, int x) {
	// insertamos x despues del ultimo elemento
	v[n] = x;
	// mientras x sea mayor que su padre...
	while(v[(n-1)/2] < v[n]) {
		// intercambiamos x con su padre
		int aux = v[(n-1)/2];
		v[(n-1)/2] = v[n];
		v[n] = aux;
		// actualizamos la posicion de x
		n = (n-1)/2;
		// y volvemos a evaluar con su nuevo padre
	}
}

/*
	Elimina la raiz del monticulo y devuelve su valor
	v  Vector de elementos (monticulo)
	n  Numero de elementos en el vector
*/
int heap_remove(int *v, int n) {
	// obtenemos el valor de la raiz
	int x = v[0];
	// movemos a la raiz el ultimo elemento del monticulo
	// y reducimos el numero de elementos en 1 (--n)
	v[0] = v[--n];
	// indice para al elemento movido
	int i=0;
	// indice para el primer hijo del elemento movido
	int h=1;
	// mientras aun haya hijos
	while(h < n) {
		// validamos si hay un segundo hijo
		// y si el valor del segundo hijo es mayor que el del primero
		if(h+1<n && v[h+1]>v[h]) {
			// en ese caso el hijo a tener en cuenta sera el segundo
			h++;			
		}
		// nos quedamos con el indice del hijo de mayor valor en "h"
		
		// si el valor del hijo "h" es mayor que el padre "i"
		if(v[i] < v[h]) {
			// intercambiamos sus valores
			int aux = v[i];
			v[i] = v[h];
			v[h] = aux;
			// actualizamos el indice del elemento movido
			i = h;
			// hallamos el indice de su nuevo primer hijo
			h = 2*i+1;
		} else {
			// terminamos el bucle
			h = n;
		}
	}
	// devolvemos el valor de la raiz
	return x;
}

/*
	Ordena un vector usando un monticulo.
	v  Vector a ordenar
	n  Numero de elementos del vector
*/
void heap_sort(int *v, int n) {
	// declara un monticulo del tamanio del vector
	int *w = new int[n];
	// inserta en el monticulo todos los elementos del vector
	for(int i=0; i<n; i++) {
		heap_insert(w,i,v[i]);
	}
	// retira cada vez la raiz del monticulo e inserta su valor
	// en el vector desde la ultima posicion hacia la primera
	for(int i=n; i>0; i--) {
		v[i-1] = heap_remove(w,i);
	}
}

/*
	Programa principal
	(Ejemplo de HeapSort)
*/
int main() {
	int *v, n;
	// pide el numero de elementos del vector
	printf("n = ");
	scanf("%d",&n);
	// crea el vector de forma dinamica
	v = new int[n];
	// pide los elementos del vector
	for(int i=0; i<n; i++) {
		printf("v[%d] = ",i);
		scanf("%d",&v[i]);
	}	
	printf("Heap Sort...\n");
	// ordena el vector usando HeapSort
	heap_sort(v,n);	
	// muestra el vector ordenado
	for(int i=0; i<n; i++) {
		printf("v[%d] = %d\n",i,v[i]);
	}	
	// fin del programa
	return 0;
}

Saludos...

7 comentarios:

  1. Excelente me salvaste la existencia, muchas gracias :P

    ResponderEliminar
  2. Jajaja... pero cambiale el nombre a las variables por lo menos... xD

    Un saludo.

    ResponderEliminar
  3. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  4. De verdad debo dejar mis gracias aqui me ayudaste demasiado amigo con esto

    ResponderEliminar
  5. Necesito este codigo pero con nodos, no con arrays.
    Quien me ayuda?

    ResponderEliminar