1
ISIS 1206
ESTRUCTURAS DE
DATOS
CLASE S7-C1
HEAPSORT
Andrés Moreno Barbosa
ML 341
dar-more@[Link]
Diapositivas adaptadas del material del curso de:
ISIS 1206 - Estructuras de Datos
Robert Sedgewick and Kevin Wayne. 2011. Algorithms (4th ed.). Addison-Wesley Professional.
2
Agenda
• Heapsort
3
Barajar un arreglo
• Realizar n intercambios aleatoriamente
public static void shuffle(int[] array)
{
Random random = new Random();
int count = [Link]; Número aleatorio entre 0 e i-1
for (int i = count; i > 1; i--)
{
swap(array, i - 1, [Link](i));
}
}
4
UTILIZAR COLAS DE PRIORIDAD PARA
IMPLEMENTAR ORDENAMIENTO
ISIS 1206 - Estructuras de Datos
5
Utilizar colas de prioridad para implementar
ordenamiento
• Si tengo un arreglo de elementos sin ordenar puedo:
– Agregar los elementos uno a uno a la cola de prioridad
(MaxPQ)
– Sacar el máximo uno a uno e irlos colocando en orden en el
arreglo
6
Utilizar colas de prioridad para implementar
ordenamiento
¿Complejidad?
public void sort(String[] a)
¿En sitio?
{
¿Es estable?
int N = [Link];
MaxPQ <String> pq = new MaxPQ <String>();
for (int i = 0; i < N; i++)
[Link](a[i]);
𝑁 ∙ log 𝑁,
for (int i = N-1; i >= 0; i--)
Arreglo extra de tamaño N,
a[i] = [Link]();
No es estable
}
7
HEAPSORT
ISIS 1206 - Estructuras de Datos
8
HeapSort
Algoritmo de ordenamiento de dos fases, en este se ve el
arreglo de entrada como un árbol binario completo.
• Construcción del heap: Se construye un binary heap con
las N claves.
• Sortdown: Eliminar repetidamente la clave máxima.
9
HeapSort
• Ver el arreglo de entrada como un árbol binario completo.
1
keys in arbitrary order S
2 O 3 R
S O R T E X A M P L E 4
T
5
E 6
X
7
A
9 10 11
8 M P L E
10
HeapSort
• Construcción del heap: Se construye un binary heap con
las N claves
X
T S
P L R A
1 2 3 4 5 6 7 8 9 10 11
M O E E X T S P L R A M O E E
Bottom-up method
11
HeapSort
• Sortdown: Eliminar repetidamente la clave máxima.
1 A
2 E 3 E
4 5 6 7
L M O P
8 9 10 11
R S T X
1 2 3 4 5 6 7 8 9 10 11
A E E L M O P R S T X
12
DEMO
ISIS 1206 - Estructuras de Datos
13
HeapSort
HeapSort (construcción del heap)
• Estrategia: Recorrer de derecha a izquierda el arreglo haciendo sink del
elemento
– No se necesita hacer sink de los elementos que están en las hojas del heap.
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (construcción del heap)
HeapSort (Ordenar)
• Estrategia: Quitar el máximo
– Igual a colas de prioridad, pero no se quita el último elemento
private Key delMax (Key x)
{
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N+1] = null;
return max;
}
32
HeapSort (Ordenar)
33
HeapSort (Ordenar)
34
HeapSort (Ordenar)
35
HeapSort (Ordenar)
36
HeapSort (Ordenar)
37
HeapSort (Ordenar)
38
HeapSort (Ordenar)
39
HeapSort (Ordenar)
40
HeapSort (Ordenar)
41
HeapSort (Ordenar)
42
HeapSort (Ordenar)
43
HeapSort (Ordenar)
44
HeapSort (Ordenar)
45
HeapSort (Ordenar)
46
HeapSort (Ordenar)
47
HeapSort (Ordenar)
48
HeapSort (Ordenar)
49
HeapSort (Ordenar)
50
HeapSort (Ordenar)
51
HeapSort (Ordenar)
52
HeapSort (Ordenar)
53
IMPLEMENTACIÓN
ISIS 1206 - Estructuras de Datos
54
HeapSort - Implementación
public class Heap {
public static void sort(Comparable[] a) {
int N = [Link];
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1) {
exch(a, 1, N);
sink(a, 1, --N);}
}
private static void sink(Comparable[] a, int k, int N)
{ /* as before */ }
private static boolean less(Comparable[] a, int i, int j)
{ /* as before */ }
private static void exch(Object[] a, int i, int j)
{ /* as before */ }
}
55
public class Heap {
public static void sort(Comparable[] a) {
int N = [Link];
for (int k = N/2; k >= 1; k--)
sink(a, k, N);
while (N > 1) {
exch(a, 1, N);
sink(a, 1, --N);}
}
private static void sink(Comparable[] a, int k, int N)
{ /* as before */ }
private static boolean less(Comparable[] a, int i, int j)
{ /* as before */ }
private static void exch(Object[] a, int i, int j)
{ /* as before */ }
}
56
ANÁLISIS DE COMPLEJIDAD
ISIS 1206 - Estructuras de Datos
57
HeapSort
En la construcción del heap se utilizan ≤ 2 N comparaciones y ≤ N intercambios.
58
HeapSort
Máximo: N-2 intercambios
Máximo dos comparaciones por intercambio
59
HeapSort
Se define la altura de un nodo en un árbol como la altura del subárbol cuya raíz es dicho
nodo. Una llave de altura k puede ser intercambiado con un máximo de k llaves debajo de
el en profundidad. Ya que hay 2ℎ−𝑘 nodos en la altura k, el total de intercambios es como
máximo:
ℎ + 2 ℎ − 1 + 4 ℎ − 2 + 8 ℎ − 3 + . . . + 2ℎ 0 = 2ℎ+1 − ℎ − 2
=𝑁− ℎ−1
≤𝑁
60
HeapSort
Heapsort utiliza ≤ 2𝑁lg𝑁 comparaciones e intercambios
• Algoritmo de ordenamiento in situ con 𝑁𝑙𝑜𝑔𝑁 en el peor
caso.
– Mergesort: no, espacio extra lineal.
– Quicksort: no, tiempo cuadrático en el peor de los casos.
– Heapsort: ¡sí!
61
HeapSort
Heapsort es óptimo tanto para el tiempo como para el
espacio, pero:
• Toma más tiempo en el ciclo que un quicksort
• Hace un mal uso de la memoria caché.
• No es estable.
HeapSort (otras características)
HeapSort Peor caso
Comparacion 2N log N+2N
Intercambio 2N log N + N
• HeapSort: Optimo para espacio y tiempo, pero:
– Toma más tiempo en el ciclo que un quicksort
– No es estable
– Uso del cache de memoria
63
HeapSort