CAPÍTULO 5: ALGORITMOS DE SORTEO AVANZADOS

HeapSort

En los capítulos anteriores aprendimos lo siguiente:

Un Heap es un árbol lleno en la parte izquierda, con las siguientes características:

HeapSort es un algoritmo de sorteo inventado en 1060 por Robert W. Floyd y J. W. J Williams, su complejidad es O(n log n) para sortear n elementos, HeapSort opera in place pero no es estable, es decir, no conserva el orden en que aparecen los objetos al terminar de sortear.

HeapSort hace uso de un (MinHeap: de mayor a menor o MaxHeap: de menor a mayor) como estructura base, recordemos que el Heap nos permite guardar datos sorteados de manera compacta y permite operaciones de borrar o agregar elementos de manera rápida.

El principio de HeapgeSort usando un MaxHeap lo resumimos de la siguiente manera:

• Tomamos el array con los elementos que queremos sortear y construimos un MaxHeap.

• Cuando el MaxHeap ya esté listo, Extraemos el elemento en la raíz, el cual será el mayor de todos y en su lugar colocamos el último [2] elemento en el MaxHeap.

• Este elemento que extraemos de la raíz es el mayor de todos y por lo tanto ya está sorteado en su posición final, entonces lo marcamos como sorteado y no lo tenemos en cuenta para los siguientes llamados del algoritmo (lo sacamos del heap).

• Repetimos el proceso extrayendo el máximo elemento en la raíz y reestableciendo la cualidad del MaxHeap, al colocar el nuevo elemento que movimos a la raíz, en su posición en correcta en el Heap [3], hasta que todos los elementos estén marcados como sorteados y el MaxHeap este vacío.

Implementación de HeapSort

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

	namespace HeapSort {

		void swap(int& a, int& b) {
			int h = b;
			b = a;
			a = h;
		}

		void Heapify(int a[], int l, int root) {
			int largest, left = (root) * 2 + 1, right = (root) * 2 + 2;
			if (left <= l && a[left]>a[root])
				largest = left;
			else largest = root;
			if (right <= l && a[right]>a[largest])
				largest = right;
			if (largest != root) {
				swap(a[root], a[largest]);
				Heapify(a, l, largest);
			}
		}

		void BuildMaxHeap(int a[], int l) {
			for (int i = (l - 1) / 2; i >= 0; i--)
				Heapify(a, l, i);
		}

		void Heapsort(int a[], int f, int l) {
			BuildMaxHeap(a, l);
			for (int i = l; i>0; i--) {
				swap(a[0], a[i]);
				Heapify(a, i - 1, 0);
			}
		}
	}

Entendiendo Heapify

Esta función toma como argumentos

• El array (a[])
• El índice del elemento final (l) 
• El índice de la raíz (root). 

la función heapify se encarga de establecer el orden de los valores en un árbol con dos sucesores (SC), para ello usamos 4 variables:

• largest: índice del elemento más grande
• left: índice del elemento a la izquierda de la raíz
• right: índice del elemento a la derecha de la raíz
• root: índice de la raíz.

Si left es menor o igual al último índice en el array y el elemento en el índice left es mayor al elemento en la raíz: Entonces el elemento más grande está a la izquierda de la raíz, de lo contrario el elemento más grande está en la raíz. De esta manera obtenemos el mayor elemento entre estos dos índices.

Sabiendo ahora el índice del elemento más grande (entre la raíz y el elemento a su izquierda), nos falta encontrar el elemento más grande entre este largest y el elemento a la derecha de la raíz (right).

Si right está a la izquierda del último elemento y el elemento en el índice right es mayor al elemento en el índice largest encontrado previamente, entonces sabemos que el elemento más grande de este árbol con 2 SC, es el elemento a la derecha de la raíz, de lo contrario permanece largest con su valor actual, que es el mayor entre la raíz y el elemento a la izquierda de la raíz.

Ahora viene lo importante (Línea 123), para que se cumplan las condiciones de un MaxHeap, el elemento más grande debe estar siempre en la raíz, si este es el caso, la función termina, si no, entonces tenemos que poner el elemento más grande en su lugar usando la función swap() y tenemos que chequear que en ese sub árbol, donde pusimos el elemento que estaba en la raíz, también cumple esta cualidad, entonces llamamos de nuevo heapify() con largest [4] como parámetro, para el índice de la raíz que se debe chequear.

Puede que aún no este muy claro el procedimiento de HeapSort, por eso vamos a revizar la siguiente animación:

Ejemplo: Animación sorteando con HeapSort

Al tomar el último elemento (-2), el Heap queda ahora vacío y nuestra lista sorteada se vera de la siguiente manera.

Análisis de la complejidad de HeapSort

Complejidad Heapify:

Todas las acciones en la función Heapify tienen complejidad Theta(1). En Worst-Case un SC es siempre más grande que la raíz, en este caso se recorre una ruta (path) entera en el árbol. Un Heap con n elementos puede ser tan profundo como log(n). Por lo anterior deducimos:

Complejidad BuildMaxHeap:

Para la animación de HeapSort utilizamos ya un Heap previamente armado, HeapSort incluye esta tarea como paso inicial. En BuildMaxHeap, se llama la función Heapify Theta(n) veces:    

Complejidad HeapSort:

Conclusiones

• Heapsort al igual que Mergesort y Quicksort es asintóticamente óptimo.

• Sin embargo, Quicksort es por lo general más rápido que Heapsort.

• Existe una variación Bottom-Up de Heapsort, con la cual, para valores grandes de n, el tiempo de ejecución es muy cercano al de Quicksort, la idea es la siguiente:
  
  -  Reducción del número de intercambios mediante la identificación del camino (path) con número máximo de hijos.
  
  -  Recorrer el camino de abajo hacia arriba (bottom-up), hasta que se encuentre un valor, el cual es mayor al valor a equilibrar de la raíz.

• En comparación con mergesort, Heapsort no hace uso de algún array para guardar valores temporalmente, lo que significa que es en el acto, asintóticamente óptimo.

El Manual de los algoritmos y las estructuras de datos.

Este capítulo ha sido solo uno de 9 capítulos en total del libro.

Descarga el manual directamente desde este enlace:

https://leanpub.com/elmanualdelosalgoritmosylasestructurasdedatos

¿Te ha gustado?, quisieras acceder a más contenido?

Registrate y deja tu comentario!