Estructuras de Datos · Clase 26. Heapsort y cola de prioridad¶
Miércoles 11 de noviembre de 2026, de 17:00 a 19:00.
El montículo de máximos guarda un árbol binario completo en un arreglo y deja
insertar y extraer el máximo en \(O(\log n)\). La sesión lo lleva a tres usos.
El primero es construirlo a partir de un arreglo cualquiera: insertando las
claves una por una cuesta \(O(n \log n)\), y bajando cada casilla con hijos, de
la última a la raíz, cuesta \(\Theta(n)\). El segundo es ordenar con él dentro
del mismo arreglo, y ese algoritmo se llama heapsort. La STL trae las dos
cosas como funciones de <algorithm>, make_heap y sort_heap, junto con
push_heap y pop_heap. El tercero es el TAD cola de prioridad, que atiende
siempre la clave más urgente, y su versión de la STL, priority_queue, hecha
sobre esas funciones.
Al terminar, el objetivo es poder seguir a mano construir y heapsort con
el árbol y el arreglo en cada paso, demostrar que construir cuesta
\(\Theta(n)\), usar las funciones de montículo de <algorithm> en el orden que
piden, dar el contrato de la cola de prioridad con el costo de cada
operación en tres implementaciones, y usar priority_queue con enteros, con
un comparador que deja el menor arriba y con registros que definen
operator<.
Diapositivas¶
Repaso: el montículo de máximos¶
Un montículo de máximos es un árbol binario completo guardado en un arreglo,
con cada nodo mayor o igual que sus hijos (CLRS, §6.1). Con índices desde 0,
el padre de \(i\) está en \(\lfloor (i-1)/2 \rfloor\) y sus hijos en \(2i+1\) y
\(2i+2\). Insertar pone la clave en la primera casilla libre y la sube mientras
su padre sea menor; extraer el máximo pasa la última clave a la raíz y la baja
hacia el mayor de sus hijos. Las dos cuestan \(O(\log n)\), y consultar el
máximo es leer a[0].
Construir un montículo¶
Llega el arreglo 16 44 13 58 37 92 75 11 64, sin ningún orden, y hay que
volverlo un montículo de máximos dentro del mismo arreglo.
Primera idea: insertar una por una¶
Cada casilla, de la 1 en adelante, se sube como si acabara de llegar. Cuando le
toca a a[i], el prefijo a[0..i-1] ya es un montículo.
// Versión ingenua: inserta las claves una por una.
void construirSubiendo(vector<int> &a) {
int i = 1;
while (i < (int) a.size()) {
subir(a, i);
i = i + 1;
}
}
Son \(n - 1\) llamados a subir, cada uno de \(O(\log n)\): \(O(n \log n)\). El peor
caso llega con las claves en orden creciente, porque cada una es la mayor
hasta ese momento y sube hasta la raíz. En un árbol de 15 claves, las 8 del
último nivel suben tres niveles cada una: casi la mitad de las claves hace el
recorrido más largo.
Bajar de abajo arriba¶
Las casillas sin hijos ya son montículos de una clave. Con \(n\) claves, la
última casilla con hijos es la \(\lfloor n/2 \rfloor - 1\): con \(n = 9\) es la 3,
cuyo hijo izquierdo es la 7, mientras que el de la casilla 4 sería la 9, fuera
del arreglo. construir baja cada casilla desde ahí hasta la raíz (CLRS,
§6.3). Usa el bajar de monticulo.h, ahora como función sobre cualquier
vector y con el tamaño como parámetro: las casillas de n en adelante no se
miran.
// Baja la clave de i dentro de a[0..n-1].
void bajar(vector<int> &a, int n, int i) {
bool sigue = true;
while (sigue) {
int izq = 2 * i + 1;
int der = 2 * i + 2;
int mayor = i;
if (izq < n && a[izq] > a[mayor]) {
mayor = izq;
}
if (der < n && a[der] > a[mayor]) {
mayor = der;
}
if (mayor != i) {
intercambiar(a, i, mayor);
i = mayor;
} else {
sigue = false;
}
}
}
// Convierte un arreglo cualquiera en montículo de máximos.
void construir(vector<int> &a) {
int n = (int) a.size();
int i = n / 2 - 1;
while (i >= 0) {
bajar(a, n, i);
i = i - 1;
}
}
Cuando le toca a la casilla \(i\), toda casilla mayor que \(i\) ya es la raíz de
un montículo. Los dos hijos de \(i\) lo son, y con eso bajar deja un montículo
con raíz en \(i\). La traza sobre el arreglo del ejemplo:
| llamado | clave | cambia con | intercambios | queda |
|---|---|---|---|---|
bajar(3) |
58 | 64 | 1 | 16 44 13 64 37 92 75 11 58 |
bajar(2) |
13 | 92 | 1 | 16 44 92 64 37 13 75 11 58 |
bajar(1) |
44 | 64, luego 58 | 2 | 16 64 92 58 37 13 75 11 44 |
bajar(0) |
16 | 92, luego 75 | 2 | 92 64 75 58 37 13 16 11 44 |
En bajar(0) es fácil detenerse antes de tiempo. Después de cambiar con el
92, el 16 queda en la casilla 2, con hijos 13 y 75, y ahí todavía es menor que
el 75. Por eso bajar sigue hasta que la clave es mayor que sus dos hijos o
llega a una hoja. Que los dos subárboles ya fueran montículos es lo que
permite que un solo recorrido hacia abajo baste.
Con construirSubiendo el mismo arreglo queda 92 64 75 44 37 13 58 11 16,
con 8 intercambios en vez de 6. Los dos arreglos son montículos de máximos:
la propiedad no fija un único orden, y la raíz es el 92 en los dos.
Por qué cuesta \(\Theta(n)\)¶
En un árbol de 15 claves, las 8 hojas no bajan, las 4 del nivel 2 bajan a lo sumo uno, las 2 del nivel 1 a lo sumo dos y la raíz a lo sumo tres: \(4 \cdot 1 + 2 \cdot 2 + 1 \cdot 3 = 11\) intercambios. Subiendo, una clave del nivel \(d\) sube \(d\): \(2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34\). Bajando, las claves que hacen el recorrido largo son pocas.
Teorema (CLRS, §6.3). Sobre un arreglo de \(n \ge 1\) claves, construir
hace a lo sumo \(2n\) intercambios.
Demostración. Se procede de forma directa, contando los intercambios por niveles del árbol.
Desarrollo. Sea \(h = \lfloor \log_2 n \rfloor\) la altura. El nivel \(d\) tiene a lo sumo \(2^d\) casillas, y una clave que empieza en el nivel \(d\) baja a lo sumo \(h - d\) niveles, con un intercambio por nivel. Cambiando \(d\) por \(j = h - d\), que recorre los mismos valores de 0 a \(h\):
Sea \(S = \sum_{j \ge 1} j/2^j\). Restando la mitad de \(S\) término a término:
Entonces \(S = 2\). La suma hasta \(h\) tiene solo términos positivos y no pasa de 2, y como \(2^h \le n\), queda \(I(n) \le 2^h \cdot 2 \le 2n\).
Conclusión. Por lo tanto, se puede concluir que \(I(n) \le 2n\) para todo \(n \ge 1\), es decir, \(I(n) \in O(n)\) con testigos \(c = 2\) y \(k = 1\).
Cada vuelta de bajar hace dos comparaciones, y hay una vuelta por
intercambio más la última de cada llamado, así que las comparaciones son a lo
sumo \(2(2n + n/2) = 5n\): tiempo \(O(n)\) con \(c = 5\) y \(k = 1\). El ciclo visita
\(\lfloor n/2 \rfloor\) casillas, y por eso tampoco baja de lineal: \(\Theta(n)\).
La distancia \(h - d\) no es constante
Un atajo tentador dice que cada clave baja \(h - d\) niveles y que eso es una constante. No lo es: va de 0 en las hojas a \(h\) en la raíz. Lo que hace lineal la suma es que los niveles con recorridos largos tienen pocas casillas, y eso solo se ve sumando nivel por nivel, como arriba.
Con 31 claves en orden creciente la cota da exactamente lo medido: \(2^4 (1/2 + 2/4 + 3/8 + 4/16) = 26\) intercambios.
Medido¶
heapsort.cpp cuenta los intercambios de los dos caminos con las claves
\(1, 2, \ldots, n\) en orden creciente, el peor caso de los dos:
| \(n\) | construir |
construirSubiendo |
|---|---|---|
| 31 | 26 | 98 |
| 1 048 575 | 1 048 555 | 18 874 370 |
Con un millón de claves, subiendo hace 18 veces más intercambios.
| Operación | Costo | Por qué |
|---|---|---|
construirSubiendo |
\(O(n \log n)\) | cada clave sube hasta \(\lfloor \log_2 n \rfloor\) niveles, y la mitad está en el último |
construir |
\(\Theta(n)\) | la mitad son hojas y no bajan; las que bajan mucho son pocas (teorema) |
| espacio aparte, los dos | \(\Theta(1)\) | trabajan dentro del mismo arreglo, con unas pocas variables |
Heapsort¶
Para ordenar 24 57 34 68 15 46 con el montículo, la primera idea es
construir y extraer el máximo seis veces, poniendo cada uno en otro arreglo
desde el final. Cuesta \(O(n \log n)\) y pide un segundo arreglo de \(n\)
casillas.
Al extraer el máximo, el montículo pierde su última casilla, a[fin]. En el
arreglo ordenado, a esa casilla le corresponde justo el máximo de lo que queda
en el montículo, el mayor de las \(\mathit{fin} + 1\) claves por ordenar. No
hace falta otro arreglo: se cambia a[0] con a[fin], el montículo se acorta
en una casilla y la clave que llegó a la raíz baja (CLRS, §6.4).
// Ordena de menor a mayor sin arreglo auxiliar.
void heapsort(vector<int> &a) {
construir(a);
int fin = (int) a.size() - 1;
while (fin > 0) {
intercambiar(a, 0, fin);
bajar(a, fin, 0);
fin = fin - 1;
}
}
En cada vuelta, a[0..fin] es un montículo con las claves menores y
a[fin+1..n-1] tiene las mayores, ya en orden. bajar recibe fin como
tamaño y no toca la parte ordenada. construir deja 68 57 46 24 15 34, y
las rondas quedan así:
| ronda | sale a a[fin] |
nueva raíz | baja por | montículo | ordenado |
|---|---|---|---|---|---|
| \(\mathit{fin} = 5\) | 68 | 34 | 57 | 57 34 46 24 15 |
68 |
| \(\mathit{fin} = 4\) | 57 | 15 | 46 | 46 34 15 24 |
57 68 |
| \(\mathit{fin} = 3\) | 46 | 24 | 34 | 34 24 15 |
46 57 68 |
| \(\mathit{fin} = 2\) | 34 | 15 | 24 | 24 15 |
34 46 57 68 |
| \(\mathit{fin} = 1\) | 24 | 15 | 15 |
24 34 46 57 68 |
Fueron cinco rondas para seis claves, y la menor quedó en a[0] sin moverla.
Bajar sin acortar el montículo
Si heapsort llama bajar(a, n, 0) con el tamaño completo, la parte
ordenada sigue a la vista. Sobre el mismo arreglo, en la segunda ronda el
15 llega a la raíz y baja por el 46 hasta a[2]; ahí bajar ve a
a[5], el 68 que ya estaba en su lugar, y lo sube. El arreglo termina en
68 57 24 46 34 15.
| Parte | Costo | Por qué |
|---|---|---|
construir |
\(\Theta(n)\) | el teorema de la sección anterior |
| una ronda | \(O(\log n)\) | un intercambio y una bajada de a lo sumo \(\lfloor \log_2 n \rfloor\) niveles |
| las \(n - 1\) rondas | \(O(n \log n)\) | también en el peor caso: la cota de cada ronda vale para cualquier orden de llegada |
| espacio aparte | \(\Theta(1)\) | ordena dentro del mismo arreglo, y bajar es un ciclo, sin recursión |
| estable | no | el cambio de a[0] con a[fin] salta por encima de lo que hay en medio, y dos claves iguales pueden quedar invertidas |
Frente a los otros dos algoritmos que ordenan un arreglo:
| Algoritmo | Peor caso | Espacio aparte | Por qué |
|---|---|---|---|
| quicksort | \(\Theta(n^2)\) | \(\Theta(\log n)\) a \(\Theta(n)\) | depende del pivote; el espacio es la pila de llamadas |
| merge sort sobre un arreglo | \(\Theta(n \log n)\) | \(\Theta(n)\) | mezclar copia las mitades (CLRS, §2.3) |
| heapsort | \(\Theta(n \log n)\) | \(\Theta(1)\) | construir y \(n - 1\) bajadas en el mismo arreglo |
El montículo en la STL¶
<algorithm> trae cinco funciones que trabajan sobre un rango de un vector,
dado por dos iteradores, y lo mantienen en orden de montículo de máximos. No
guardan nada aparte: reordenan las casillas del rango, y cada una corresponde a
algo que ya se construyó en la sesión.
| Función | Lo que hace, con lo que se vio en clase |
|---|---|
make_heap(b, e) |
construir: baja cada casilla con hijos, desde \(\lfloor n/2 \rfloor - 1\) hasta la raíz |
push_heap(b, e) |
subir la última casilla del rango |
pop_heap(b, e) |
una ronda de heapsort: cambia la raíz con la última casilla y baja la nueva raíz en un rango una casilla más corto |
sort_heap(b, e) |
el ciclo de heapsort, sobre un rango que ya es montículo |
is_heap(b, e) |
revisa cada casilla contra su padre |
Ninguna cambia el tamaño del vector; eso lo hacen push_back y pop_back, y
el orden de las llamadas importa. Para agregar va primero push_back y después
push_heap, que sube la clave que quedó al final. Para sacar va primero
pop_heap, que deja el máximo al final, y después pop_back, que lo quita.
// Arma el montículo y agrega una clave.
void armarYAgregar(vector<int> &v) {
imprimir("arreglo:", v);
printf("is_heap: %d\n", (int) is_heap(v.begin(), v.end()));
make_heap(v.begin(), v.end());
imprimir("make_heap:", v);
printf("is_heap: %d\n", (int) is_heap(v.begin(), v.end()));
v.push_back(88);
imprimir("push_back(88):", v);
push_heap(v.begin(), v.end());
imprimir("push_heap:", v);
}
// Saca el máximo y ordena lo que queda.
void sacarYOrdenar(vector<int> &v) {
pop_heap(v.begin(), v.end());
imprimir("pop_heap:", v);
printf("back() = %d\n", v.back());
v.pop_back();
imprimir("pop_back:", v);
sort_heap(v.begin(), v.end());
imprimir("sort_heap:", v);
printf("is_heap: %d\n", (int) is_heap(v.begin(), v.end()));
}
Con las claves 36 81 49 95 53 77 91:
arreglo: 36 81 49 95 53 77 91
is_heap: 0
make_heap: 95 81 91 36 53 77 49
is_heap: 1
push_back(88): 95 81 91 36 53 77 49 88
push_heap: 95 88 91 81 53 77 49 36
pop_heap: 91 88 77 81 53 36 49 95
back() = 95
pop_back: 91 88 77 81 53 36 49
sort_heap: 36 49 53 77 81 88 91
is_heap: 0
make_heap deja el mismo arreglo que construir. push_heap sube el 88 por
encima del 36 y del 81, como subir. pop_heap cambia el 95 con el 36, baja
el 36 en las siete primeras casillas y deja el 95 en v[7], donde back() lo
lee antes del pop_back. sort_heap ordena las siete que quedan, y el
resultado ya no es un montículo de máximos. La norma de C++ no fija el arreglo
exacto que dejan estas funciones; con g++ y claves distintas coincide con el de
las funciones de la sesión, y con claves repetidas el desempate puede ser otro.
El orden de las llamadas
Con el vector en 95 88 91 81 53 77 49 36, un pop_back antes de
pop_heap saca el 36, la última casilla, y el 95 se queda. Quitar una hoja
no rompe el montículo, así que nada lo delata. Y un push_heap antes del
push_back deja la clave nueva fuera del rango, sin subir.
El de mínimos con greater()¶
greater<int>(), de <functional>, compara con a > b, como MenorArriba, y
deja el menor arriba. Cada llamada sobre ese rango lleva el mismo comparador.
// Con greater<int>() el menor queda en w[0].
void minimos() {
int claves[7] = {36, 81, 49, 95, 53, 77, 91};
vector<int> w(claves, claves + 7);
make_heap(w.begin(), w.end(), greater<int>());
imprimir("min make_heap:", w);
pop_heap(w.begin(), w.end(), greater<int>());
printf("sale el menor: %d\n", w.back());
w.pop_back();
imprimir("min pop_back:", w);
}
Queda 36 53 49 95 81 77 91, con el 36 en w[0]; pop_heap lo lleva al
final, y tras el pop_back quedan 49 53 77 95 81 91.
| Función | Costo | Por qué |
|---|---|---|
make_heap |
\(\Theta(n)\) | a lo sumo \(3n\) comparaciones, por el mismo argumento de construir |
push_heap |
\(O(\log n)\) | la última clave sube por un camino de largo \(\lfloor \log_2 n \rfloor\) |
pop_heap |
\(O(\log n)\) | un intercambio y una bajada |
sort_heap |
\(O(n \log n)\) | \(n - 1\) veces lo de pop_heap |
is_heap |
\(O(n)\) | cada casilla contra su padre, hasta la primera que falle |
| espacio aparte | \(\Theta(1)\) | todo pasa dentro del mismo vector |
El TAD cola de prioridad¶
En una sala de urgencias cada paciente recibe al llegar una gravedad de 1 a 5. Una cola que atiende por orden de llegada haría esperar al paciente grave que llegó último detrás de todos los leves. Se atiende primero al de mayor gravedad, sin importar cuándo llegó: hace falta una cola de prioridad, en la que sale primero la clave de mayor prioridad (CLRS, §6.5). Por dentro las claves no tienen un orden visible; el contrato solo promete cuál sale.
| Operación | Precondición | Resultado |
|---|---|---|
insertar(k) |
ninguna | k queda en la cola, aunque ya haya otra igual |
maximo() |
la cola no está vacía | devuelve la clave mayor, sin quitarla |
extraerMax() |
la cola no está vacía | quita la clave mayor y la devuelve |
vacio(), tamano() |
ninguna | si hay claves y cuántas |
Una cola de prioridad de mínimos es igual con la clave menor: minimo() y
extraerMin(). La clase Monticulo de la sesión anterior cumple el contrato
de máximos:
// Las operaciones del TAD sobre el montículo de máximos.
void conMonticulo() {
Monticulo cola;
cola.insertar(61);
cola.insertar(27);
printf("maximo() = %d\n", cola.maximo());
cola.insertar(88);
cola.insertar(43);
printf("extraerMax() = %d\n", cola.extraerMax());
printf("extraerMax() = %d\n", cola.extraerMax());
cola.insertar(70);
printf("tamano() = %d, maximo() = %d\n", cola.tamano(), cola.maximo());
}
maximo() = 61
extraerMax() = 88
extraerMax() = 61
tamano() = 3, maximo() = 70
maximo() consulta y no quita: después de él, el 61 sigue en la cola. El 88
entró de tercero y sale primero.
| Estructura | insertar |
maximo |
extraerMax |
espacio | Por qué |
|---|---|---|---|---|---|
| arreglo sin orden | \(\Theta(1)\) | \(\Theta(n)\) | \(\Theta(n)\) | \(\Theta(n)\) | hay que buscar el mayor |
| arreglo ordenado | \(\Theta(n)\) | \(\Theta(1)\) | \(\Theta(1)\) | \(\Theta(n)\) | hay que correr las claves para abrir espacio |
| montículo | \(O(\log n)\) | \(\Theta(1)\) | \(O(\log n)\) | \(\Theta(n)\) | la clave sube o baja por un camino de largo \(\lfloor \log_2 n \rfloor\) |
Con \(n\) inserciones y \(n\) extracciones, los dos arreglos cuestan \(\Theta(n^2)\) en el peor caso y el montículo \(O(n \log n)\).
El contenedor priority_queue¶
priority_queue<T> se incluye con #include <queue> y está hecha sobre las
funciones de la sección anterior: guarda un vector, push es push_back y
push_heap, y pop es pop_heap y pop_back.
// push, top, pop, size y empty: sale siempre el mayor.
void enteros() {
priority_queue<int> pq;
int llegan[5] = {64, 15, 90, 37, 52};
int i = 0;
while (i < 5) {
pq.push(llegan[i]);
i = i + 1;
}
printf("top() = %d, size() = %d\n", pq.top(), (int) pq.size());
pq.pop();
printf("tras pop(): top() = %d\n", pq.top());
printf("salen:");
while (!pq.empty()) {
printf(" %d", pq.top());
pq.pop();
}
printf("\n");
}
top() = 90, size() = 5
tras pop(): top() = 64
salen: 64 52 37 15
pop() no devuelve nada
int x = pq.pop(); no compila: pop es void. Primero se lee con
top() y después se saca con pop(), y las dos exigen que la cola no
esté vacía. Que pop no devuelva valor no lo hace in place: esa
palabra describe un algoritmo que trabaja sin memoria auxiliar
proporcional a la entrada, como heapsort.
El menor arriba¶
El tercer parámetro de la plantilla es un struct comparador, como los que se
usaron con map. Dice cuándo a va detrás de b: con a > b, el mayor va
detrás y arriba queda el menor.
// a va detrás de b cuando a es mayor: arriba queda el menor.
struct MenorArriba {
bool operator()(int a, int b) const {
return a > b;
}
};
Con priority_queue<int, vector<int>, MenorArriba> y las claves
71 55 83 9 55, salen 9 55 55 71 83: un montículo de mínimos, que guarda el
55 dos veces.
Registros con operator<¶
// Un paciente: más gravedad se atiende antes y,
// con la misma gravedad, el que llegó primero.
struct Paciente {
int llegada;
int gravedad;
bool operator<(const Paciente &o) const {
bool menos;
if (gravedad != o.gravedad) {
menos = gravedad < o.gravedad;
} else {
menos = llegada > o.llegada;
}
return menos;
}
};
a < b quiere decir que a es menos urgente y sale después. Con cinco
pacientes de gravedades 3 1 4 3 4, en ese orden de llegada:
atender: llegada 3, gravedad 4
atender: llegada 5, gravedad 4
atender: llegada 1, gravedad 3
atender: llegada 4, gravedad 3
atender: llegada 2, gravedad 1
Entre los de gravedad 4 sale primero el 3, que llegó antes. Sin el desempate por llegada, el orden entre iguales lo decidiría la biblioteca.
| Operación | Costo | Por qué |
|---|---|---|
push(k) |
\(O(\log n)\) | push_back y push_heap |
pop() |
\(O(\log n)\) | pop_heap y pop_back |
top(), size(), empty() |
\(\Theta(1)\) | top lee la casilla 0 |
priority_queue<int> pq(v.begin(), v.end()) |
\(\Theta(n)\) | copia el rango y llama make_heap |
| espacio | \(\Theta(n)\) | las claves en el vector, sin punteros |
priority_queue no tiene iteradores: para ver todas las claves hay que
sacarlas.
Para practicar en casa¶
Propuesto 1: construir a mano¶
Apliquen construir a 21 6 39 14 52 30 47 9 y dibujen el árbol después de
cada llamado a bajar. Empieza en \(i = 3\) y queda 52 21 47 14 6 30 39 9.
Propuesto 2: heapsort a mano¶
Sigan heapsort sobre 5 13 2 25 7 17 20 8 4, el arreglo de los ejercicios
de CLRS, §6.4. El montículo inicial es 25 13 20 8 7 17 2 5 4, y tras la
primera ronda queda 20 13 17 8 7 4 2 5 | 25.
Propuesto 3: de mayor a menor¶
Cambien heapsort para que ordene de mayor a menor. Hace falta un montículo de
mínimos, así que cambian las dos comparaciones de bajar.
Propuesto 4: UVa 10954, Add All¶
Una cola de mínimos con monticulo.h cambiado a mínimos, o priority_queue
con el comparador de la sesión. El enunciado, las trampas y la lectura están
en Para el juez.
Propuesto 5: un paciente empeora¶
Mientras espera, la gravedad de un paciente sube. ¿Qué operación le falta al
montículo para reflejarlo, y cuánto costaría si se supiera en qué casilla está?
Piensen en cuál de las dos, subir o bajar, sirve cuando una clave crece
(CLRS, §6.5).
Para el juez¶
La solución lee la entrada de ejemplo del enunciado y reproduce su salida:
./sol < uva10954.in.
UVa 10954, Add All¶
UVa 10954, Add All: https://vjudge.net/problem/UVA-10954, donde también se envía. La página pide cuenta.
Sumar dos números cuesta su suma. Cada caso trae \(N\) enteros positivos, con
\(2 \le N \le 5000\), todos menores que 100 000, y hay que sumarlos todos, de a
dos, con el menor costo total. Los casos terminan con \(N = 0\), que no se
procesa. Para 1 2 3, sumar \(1 + 2\) cuesta 3 y luego \(3 + 3\) cuesta 6, en
total 9; empezando por \(2 + 3\) el total es 11.
Se suman siempre los dos menores que quedan, y la suma vuelve al grupo. Para
1 2 3 4: \(1 + 2 = 3\), después \(3 + 3 = 6\) y al final \(6 + 4 = 10\), en total
19. Una cola de prioridad de mínimos da los dos menores en \(O(\log N)\): dos
extraerMin y un insertar por suma, \(O(N \log N)\) por caso y \(\Theta(N)\) de
espacio.
Las trampas
- Ordenar una vez y sumar de izquierda a derecha no basta: con
5 5 5 5da \(10 + 15 + 20 = 45\), y la cola da \(10 + 10 + 20 = 40\). La suma nueva puede ser mayor que las que quedan, y tiene que volver al grupo. - Con 5000 números de 99 999 el total pasa de 6 000 millones, más de lo que
cabe en un
int: se acumula enlong longy se imprime con%lld. Las sumas parciales sí caben en unint, porque ninguna pasa de \(5000 \cdot 99\,999\).
La lectura: el ciclo de afuera lee \(N\) y para en el 0 final o si la entrada se acaba antes; el de adentro lee los \(N\) números.
int n;
while (scanf("%d", &n) == 1 && n != 0) {
int i = 0;
while (i < n) {
int x;
scanf("%d", &x);
// la clave x entra a la cola de minimos
i = i + 1;
}
// sumar los dos menores mientras quede mas de uno
// e imprimir el costo con printf("%lld\n", costo)
}
Solución: uva10954.cpp, con el montículo de mínimos monticulo_min.h, entrada y salida.
Lo que se vio¶
construirbaja cada casilla con hijos, desde \(\lfloor n/2 \rfloor - 1\) hasta la raíz, y cuesta \(\Theta(n)\); insertar una por una cuesta \(O(n \log n)\).- Heapsort cambia el máximo con
a[fin]y baja la nueva raíz en un montículo una casilla más corto: \(O(n \log n)\) en el peor caso y \(\Theta(1)\) de espacio aparte, sin ser estable. make_heap,push_heap,pop_heapysort_heaphacen sobre unvectorlo deconstruir,subir, una ronda de heapsort y heapsort; el tamaño lo cambianpush_backantes depush_heapypop_backdespués depop_heap.- La cola de prioridad promete insertar, consultar y extraer la clave mayor;
con un montículo cuestan \(O(\log n)\), \(\Theta(1)\) y \(O(\log n)\), y eso es
priority_queue, que con un comparador deja el menor arriba.
Ejercicios interactivos¶
Las actividades para trabajar en el navegador, ordenadas por los temas de la sesión, están en Ejercicios interactivos. Los arreglos y los programas no son los de la sesión: mismo tema, ronda nueva.
Lo que sigue¶
Las estructuras de datos que trae Python y lo que cuesta cada operación, frente a los contenedores de C++ que ya se vieron.
Código de la sesión¶
Compilación y ejecución:
g++ -Wall -Wextra archivo.cpp -o archivo && ./archivo
- monticulo.h: la clase
Monticulode la sesión anterior, queuso_cola.cppusa como cola de prioridad. - heapsort.cpp:
bajarcon el tamaño aparte,construirSubiendo,construir,heapsorty la versión que no acorta el montículo, con las trazas y el conteo del peor caso, y su salida. - uso_cola.cpp: el TAD sobre
Monticuloypriority_queuecon enteros, conMenorArribay conPaciente, con salida. - stl_heap.cpp:
make_heap,push_heap,pop_heap,sort_heapeis_heapsobre unvector, y el de mínimos congreater<int>(), con salida. - monticulo_min.h: el montículo de mínimos,
monticulo.hcon las comparaciones al revés.
La solución del problema de juez está en la sección Para el juez, con su entrada y su salida.
Referencias¶
- T. H. Cormen, C. E. Leiserson, R. L. Rivest y C. Stein. Introduction to Algorithms, 4.ª ed. MIT Press, 2022. Capítulo 6, Heapsort: §6.1, montículos; §6.3, construir un montículo; §6.4, el algoritmo heapsort; §6.5, colas de prioridad. §2.3, merge sort.
- cppreference. std::make_heap, std::push_heap, std::pop_heap, std::sort_heap y std::priority_queue: https://en.cppreference.com/w/cpp/algorithm/make_heap.
- UVa, en Virtual Judge. Problema 10954, Add All: https://vjudge.net/problem/UVA-10954.