Ordenamiento, Heapsort y Colas de prioridad
Agustn J. Gonzlez ELO 320: Estructura de Datos y Algoritmos
Ordenamiento y Estadsticas de Orden
Problema de ordenamiento: Entrada: Una secuencia de n nmeros (a1,a2, ..., an) Salida: Una permutacin (a1, a2, a3,...,an) de la entrada tal que a1e a2 e a3 e... e an Soluciones:
Insertion-Sort, merge-sort, heapsort, quicksort. ---> ;(n lg n)
La estadstica de orden i-simo de un conjunto de n nmeros, es el i-simo nmero ms pequeo. ---> O(n)
2
Heapsort
La estructura de datos heap es un arreglo de objetos que pueden ser vistos como un rbol binario completo (slo pueden faltar nodos al final del ltimo nivel). 1 Ej. 6
1 4 8 2 4 7 1 9 1 0 3
1 2 3 4 5 6 7 8 9 10 16 |14 |10 | 8 | 7 | 9 | 3 | 2 | 4 | 1
3
Propiedades del heap
El arreglo puede contener ms entradas (=length(A)) que el heap (=heap_size(A)) Obviamente heap_size(A) e length(A) La raz del rbol es A[1A (Con ndices partiendo de 1 aqu) Dado un ndice i de un nodo, su padre, hijo izquierdo e hijo derecho son determinados como: Parent(i) 1 2 3 4 5 6 7 8 9 10 return i/2 Left(i) 16 |14 |10 | 8 | 7 | 9 | 3 | 2 | 4 | 1 return 2i Right(i) return 2i+1 Estos procedimientos se pueden implementar como macros o cdigo in-line . Propiedad heap : A [Parent(i)Au A [iA para todo nodo diferente de la raz. 4
Procedimientos bsicos usados en algoritmos de ordenamiento y en colas de prioridad
Heapify(A,i): Entrada: Left(i) y Right(i) son heaps, pero A[iA puede ser menor que sus hijos. Salida: Heapify mueve A[iA hacia abajo para que el sub-rbol con raz i sea un heap.
Heapify(A,i) le= Feft(i) ri= Right(i) if( le <= heap_size(A) && A[leA > A[iA ) largest = le else largest = i if ( ri <= heap_size(A) && A[riA > A[largestA ) largest = ri if (largest != i) exchange A[iA <-> A[largestA Heapify(A, largest)
5 (1)
O (tamao
subrbol) 5
Anlisis de tiempo de Ejecucin de Heapify
T(n) = 5(1) + Tiempo de Heapify sobre uno de los sub-rboles. El peor caso para el tamao del sub-rbol es 2n/3. ste ocurre cuando la ltima fila est la mitad llena.
2n/3
n/3
T(n) e T(2n/3) + 5(1) ==> T(n) = O(lg n)
6
Construccin del heap: Build_Heap
La construccin del heap se logra aplicando la funcin heapify de manera de cubrir el arreglo desde abajo hacia arriba. Notar que los nodos hojas, ya son heap. stos estn en A[ (n/2+1) .. nA. El procedimiento Build_Heap va a travs de los nodos restantes y corre heapify en cada uno.
Build_Heap(A) { heap_size [AA = length [AA for i = length(A) /2 downto 1 do Heapify(A,i) } Ejemplo: 4 | 1 | 3 | 2 | 16 | 9 | 10 | 14 | 8 | 7
7
Anlisis del tiempo de ejecucin
Cada llamado a Heapify tiene un costo O(lgn) y como a lo ms hay n de estos llamados, una cota superior para el costo de Build_heap es O(nlgn). Un mejor anlisis conduce a O(n) Cuntos subrboles (nodos) de altura h hay como mximo? n/2h+1 Para subrboles (nodos) de altura h el costo de Heapify es O(lgn)= O(h). lg n lg n h n Luego el costo es h 1 O(h) ! O n h
h!0
h !0
h 1/ 2 ! 2h (1 1 / 2) 2 ! 2 h!0
@ Build_Heap puede ser acotado por: lgn h O n h h !0 2 g h ! O n h h !0 2 ! O( n * 2) ! O( n)
Algoritmo Heapsort
1.- Construir un heap invocando a Build_Heap 2.- Intercambiar el primer elemento, la raz y mayor elemento, del heap con el ltimo. 3.- Restituir la propiedad heap en el heap de n-1 elementos.
Heapsort(A) Build_Heap(A) for (i= lenght(A) downto 2 ) do exchange A[1A <-> A[iA heap_size [AA = heap_size [AA-1 Heapify(A,1)
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(lgn).
Colas de Prioridad
Heapsort es muy bueno, pero es superado por quicksort (lo veremos luego). La aplicacin ms popular de heapsort es para implementar colas de prioridad. Una cola de prioridad es una estructura de datos que mantiene un conjunto S de elementos cada uno asociado con una clave key. La cola de prioridad soporta las siguientes operaciones: Insert(S,x): inserta x en el conjunto S Maximum(S): retorna el elemento con mayor clave. Extract-Max(S): remueve y retorna el elemento con mayor clave. Aplicaciones: - Itineracin de tareas en sistemas de tiempo compartido - Colas de prioridad en simuladores conducidos por evento (Eventdriven simulator)
10
Operaciones en Colas de prioridad
Heap_Maximum(S): retorna el nodo raz en tiempo U(1). Heap_Extract_Max(A) if heap_size[A] <1 then error Heap undeflow max = A[1] A[1] = A[heap_size [A]] heap_size [A] = heap_size [A]-1 Heapify(A,1) return max
Tiempo de Heap_Extract_Max : O(lg n) bsicamente el tiempo de Heapify
Heap_Insert(A, key) heap_size [A] = heap_size [A]+1 i = heap_size [A] while (i > 1 and A[Parent(i)] < key) do A[i] = A[Parent(i)] i = Parent(i) A[i] = key
Tiempo de Heap_Insert : O(lg n) porque es el recorrido desde la nueva hoja a la raz. 11
Divertimento
Se trata de colorear 9 vrtices de esta estrella. Para ello usted debe partir de un vrtice no coloreado, avanzar en lnea recta con caminos de largo 2 y podr colorear el vertice de llegada. Puede usted colorear nueve vrtices?
2 1
12
