Algoritmo de Ordenamiento Heapsort
Integrantes:
Daniel Saigua Labre
Edwin Ullaguari León
Miguel Murillo Arteaga
Yu Chen Tai
Materia:
Análisis de Algoritmos
Profesora:
Phd. Ana Tapia Rosero
Fecha:
28 de noviembre de 2018
Paralelo #1
¿Qué es un Heapsort?
Heapsort es una técnica de ordenamiento basada en comparación que utiliza una estructura
de datos montón binario (Binary Heap). Es similar a Selection Sort en donde se encuentra el
máximo elemento del arreglo y se lo coloca al final, repitiendo el mismo proceso para los
elementos restantes.
¿Qué es un Binary Heap?
Primeramente, se definirá al árbol binario (Binary Tree) completo. El mismo es un árbol
binario en el cual cada nivel, excepto posiblemente el último, está completamente lleno, y
todos los nodos están lo más a la izquierda posible.
Un Binary Heap es un árbol binario completo en donde los elementos están guardados en
un ordenamiento peculiar de tal forma que el valor en un nodo padre es mayor que los valores
en sus dos nodos hijos, aunque también podría ser, al contrario. El primero se llama máximo
montón (Max Heap) y el último se llama mínimo montón (Min Heap). El montón se puede
representar por un árbol binario o por un arreglo.
Dado que un Binary Heap es un árbol binario
completo, también se puede representar fácilmente
como un arreglo. Por ello si el nodo padre se
almacena en el índice i, el hijo izquierdo se puede
Figura 1. Ejemplo de un Binary Heap calcular con 2i+1 y el hijo derecho con 2i+2 para
indexaciones que empiezan desde el valor cero. Para indexaciones que inician desde el valor
uno se tiene 2i para el hijo izquierdo y 2i+1 para el hijo derecho.
Algoritmo HeapSort para ordenar crecientemente
De manera general el algoritmo HeapSort se define en tres pasos, los cuales se especifican
a continuación:
1. Construir un Max Heap con los datos de entrada.
2. En este punto, el elemento más grande está guardado en la raíz del Heap. Se procede a
reemplazarlo con el último elemento del Heap, para luego reducir el tamaño de este
último en una unidad entera. Finalmente, se aplica el método llamado Heapify a la
raíz del árbol.
3. Se repiten los puntos arriba mencionados mientras el tamaño del Heap sea mayor a
uno.
Implementación de Heapify
El método Heapify tendrá como parámetros de entrada al arreglo y un valor entero
denominado i que servirá como índice para darle uso a cada posición del arreglo:
● Entrada: Left(i) y Right(i) son heaps, pero A[i] puede ser menor que sus hijos.
● Salida: Heapify mueve A[i] hacia abajo para que al subárbol con raíz i sea un heap.
Figura 2. Implementación del método Heapify
Tiempo de ejecución de Heapify
● T(n) = Θ (1) + Tiempo de Heapify sobre uno de los sub-árboles.
● Ahora tomando en cuenta el peor caso, para la medida del subárbol es 2n/3. Esto
sucede cuando la fila final está la mitad completa.
Figura 4. Tiempo de Ejecución
Figura 3. Análisis del Tiempo de Ejecución
Construyendo el heap: Build_Heap
● La construcción del heap se logra aplicando la función heapify de manera de cubrir el
arreglo desde abajo hacia arriba.
● Observar que los nodos hojas, ya ahora son heap. Éstos están en A [⌊ (n/2+1) ⌋.. n].
● El método Build_Heap va a través de los nodos sobrantes y trabaja con heapify en
cada uno.
Figura 5. Implementación de método Build_Heap
Ejemplo:
Análisis del tiempo de ejecución
● Cada llamado a Heapify tiene un costo O (lg n) y a lo mucho existirá n llamados de
este, una cota superior para el costo de Build_heap es O (n lg n).
● Un preferible análisis y estudio nos lleva a O(n)
● ¿Cuántos nodos hay de altura h? n/2h+1
● Para nodos de altura h el costo de Heapify es O(h).
● Luego el costo es
Implementación de Algoritmo HeapSort
1. Construir un heap invocando a Build_Heap.
2. Cambiar el elemento inicial, la raíz y mayor elemento, del heap con el último.
3. Restaurar la función principal del montículo en el montículo de n-1 elementos.
Figura 6. Implementación de HeapSort
El costo de Heapsort es O (n lg n) porque el llamado a Build_Heap toma O(n) y luego
tenemos n-1 llamados a Heapify cuyo tiempo es O (lg n).
Aplicaciones del Heapsort
El HeapSort se usa en problemas como:
1. Ordenar un arreglo casi ordenado
2. Encontrar los elementos más grandes (o pequeños) de un arreglo.
3. Una de las grandes aplicaciones de Heapsort es construir colas de prioridad con la
finalidad de que encuentre los procesos que tienen la mayor carga de prioridad dado
una gran cantidad de procesos por hacer.
4. También es muy utilizado en la programación de intervalos, imaginemos que nos dan
una lista de actividades con un tiempo determinado. Con lo cual se dice que un
algoritmo que trate de ordenar la lista de actividades nuevamente dependerá
eficientemente en un algoritmo de ordenamiento, y el método heapsort puede realizar
tal función.
Referencias
Aggarwal, S. (2013, Marzo 16). [Link]. Recuperado de:
[Link]
Ramírez Manzanares, A. (2018, Septiembre 24). Heaps y Heapsort. `
Recuperado de: [Link]
[Link]/teaching/mat/discretas/ad17/proyecto/[Link]
González, A.J. (2015, Junio 4). ELO 320: Estructura de Datos y Algoritmos.
Recuperado de: [Link]