Sede Tuluá
HeapSort y QuickSort
Fundamentos de Análisis y Diseño de Algoritmos
Montículo (Heap)
Sede Tuluá
► El algoritmo HeapSort está basado en la estructura de un montículo.
1 2 3 4 5 6 7 8 9 10
Montículo (Heap)
Sede Tuluá
► Es un arreglo de objetos que puede ser
visto como un árbol binario completo.
► Deben cumplir dos propiedades:
• Propiedad de Orden
• Propiedad de forma
1 2 3 4 5 6 7 8 9 10
Montículo (Heap)
Sede Tuluá
► Es un arreglo de objetos que puede ser visto
como un árbol binario completo.
► Deben cumplir dos propiedades:
• Propiedad de Orden:
• La raíz del árbol tiene la llave de menor valor en
todo el árbol: Montículo mínimo. (La regla se
cumple recursivamente en los subárboles)
• La raíz del árbol tiene la llave de mayor valor en
todo el árbol: Montículo máximo. (La regla se
cumple recursivamente en los subárboles)
• Propiedad de forma:
• Las hojas tienen altura h o h-1, donde h es la altura
del árbol. Cuando una hoja tiene altura h-1, todas
las hojas hacia la derecha tendrán la misma altura.
Montículo (Heap)
Sede Tuluá
► Un arreglo A que representa un montículo tiene dos atributos:
• length[A]: Número de elementos en el arreglo
• heapsize[A]: Número de elementos en el montículo.
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
► Así, se cumplen las siguientes propiedades:
• heapsize[A] ≤ legth[A]
• La raíz del árbol es A[1]
Dado el índice i de un nodo:
• Parent[i] = floor(i/2)
• Left[i] = 2.i
• Right[i] = 2.i + 1
Max-Heapify
Sede Tuluá
► Este algoritmo permite garantizar la propiedad de orden de un montículo
máximo.
Inserción en Montículos
Sede Tuluá
► La inserción en un montículo implica agregar el nodo en el último
nivel del árbol, completándolo de izquierda a derecha.
► Si el montículo es máximo, se debe garantizar que las raíces tengan
el nodo de mayor valor.
Creación en Montículos
Sede Tuluá
► La creación de un montículo a partir de un arreglo, garantiza la
propiedad de forma almacenando los datos de izquierda a derecha y
no se pueden pasar los elementos al siguiente nivel hasta que el nivel
anterior esté lleno.
► Si el montículo es máximo, se invoca el procedimiento Max-Heapify,
desde la última raíz hasta la raíz del árbol, garantizando la propiedad
de orden.
Eliminación en Montículos
Sede Tuluá
► Solamente es posible eliminar la raíz del montículo.
► Se toma el elemento de la posición que debe quedar vacía, colocándolo en la
raíz (así cumpliendo la propiedad de árbol completo), y luego intercambiar
ese valor con el máximo de sus hijos hasta satisfacer la propiedad de
montículo (si es de máximos)
Algoritmo HeapSort
Sede Tuluá
► Es un algoritmo de ordenamiento basado en comparaciones de
elementos que utiliza un heap para ordenarlos.
► Es un algoritmo de ordenamiento no recursivo, con complejidad O(n
log n).
► El ordenamiento Heapsort consiste en almacenar todos los elementos
del vector a ordenar en un montículo y luego extraer el nodo que
queda como raíz en sucesivas iteraciones obteniendo el conjunto
ordenado.
Algoritmo HeapSort
Sede Tuluá
► Ejemplo: Ordenar la siguiente sucesión:
Algoritmo HeapSort
Sede Tuluá
► Etapa 1: Organizar el arreglo de entrada como un montículo
98 89 657 7 82 4 65 91 3
897
98 657
7 82 4 65
1 3
Algoritmo HeapSort
Sede Tuluá
► Etapa 2: El elemento en la cima del heap se elimina del árbol (se
ubica en la posición final del arreglo). El resto del arreglo se organiza
restituyendo el orden del heap de repite hasta que el arbol queda sin
elementos.
8 7 657 3 82 4 65 91 9
8
7 657
3 82 4 65
1
Algoritmo HeapSort
Sede Tuluá
► Etapa 2 (Continuación)
7 3 657 1 82 4 65 8 9
7
3 657
1 82 4 65
Algoritmo HeapSort
Sede Tuluá
► Etapa 2 (Continuación)
6 3 5 1 82 4 7 8 9
6
3 5
1 82 4
Algoritmo HeapSort
Sede Tuluá
► Etapa 2 (Continuación): El procedimiento sigue hasta tener un
montículo vacío.
1 2 3 4 5 6 7 8 9
1
► ARREGLO ORDENADO:
1 2 3 4 5 6 7 8 9
Algoritmo HeapSort
Sede Tuluá
► Heapsort(A)
Build_Heap(A)
for (i= lenght(A) downto 2 ) do
exchange A[1 <-> A[i
heap_size [A = heap_size [A-1
Heapify(A,1)
Colas de Prioridad
Sede Tuluá
► Aplicación de montículos.
► Estructura de datos con un campo llave (key) que determina la prioridad.
► Operaciones de un cola de prioridad máxima:
• Insert(S, x)
• Maximum(S)
• ExtractMax(S)
• INCREASEKEY(S,x,k)
Algoritmo QuickSort
Sede Tuluá
► Basado en Dividir y Conquistar
► Pasos:
• Dividir: el arreglo se particiona en dos subarreglos no vacíos, tal que
cada elemento de un subarreglo sea menor o igual a los elementos del
otro subarreglo.
• Conquistar: los dos arreglos son ordenados llamando recursivamente a
quicksort.
• Combinar: Como cada arreglo ya está ordenado, no serequiere trabajo
adicional.
Algoritmo QuickSort
Sede Tuluá
Partition(A,p,r) {
x=A[p];
i=p1;
Quicksort(A,p,r){ j=r+1;
if (p<r) { while(1) {
q = Partition(A,p,r); do j;
Quicksort(A,p,q); until (A[j] x)
Quicksort(A,q+1, r); do i++;
} until (A[i] x)
} if (i < j)
exchange A[i] <> A[j];
else
return j;
}
}
Algoritmo QuickSort
Sede Tuluá
► Ejemplo: Ordenar la sucesión 5|3|2|6|4|1|3|7
► Proceso:
5|3|2|6|4|1|3|7 5|3|2|6|4|1|3|7
i j i j
3|3|2|6|4|1|5|7 3|3|2|6|4|1|5|7
i j i j
3|3|2|1|4|6|5|7 3|3|2|1|4|6|5|7
i j j i Retorna j
Algoritmo QuickSort
Sede Tuluá
Tiempos de Ejecución:
► Peor caso: Ocurre cuando el arreglo es particionado en n-1 y 1
elemento cada vez.
En este caso se tiene:
T(n)=T(n-1) + (n) = (n2)
► Mejor caso: Ocurre cuando Partition produce dos regiones de igual
tamaño. En este caso se tiene: T(n)=2T(n/2)+ (n) , de lo cual resulta
T(n) = (n lg n)
► Caso Promedio: T(n)= (n lg n)
Preguntas
Sede Tuluá
