Guia Heap
Heap
1. ¿Que es un Heap?
Estructura que siempre te entrega, de un solo paso, el elemento mas importante. No ordena
todo: solo mantiene al "ganador" arriba.
Es un arbol binario que se llena por niveles (izq a der), pero guardado como arreglo. La
posicion en el arreglo dice quien es el padre y quienes los hijos.
max-heap → padre > hijos → raiz = el mayor.
min-heap → padre < hijos → raiz = el menor.
Para no escribir dos clases distintas: el Heap recibe un comparador en el constructor.
Adentro nunca se usa > ni < directamente, se llama a compara(a, b) . La regla del
comparador es:
compara(a, b) == true significa "a va antes que b" (a tiene mas prioridad).
Asi, con el mismo Heap, eliges max o min eligiendo el comparador al crearlo.
¿Donde se usa?
El patron es siempre el mismo: en cada paso necesitas "el mejor" de un conjunto que va
cambiando. Cuando aparece eso, piensa en heap.
Triaje en emergencias Cotizaciones / mejor precio
max-heap min-heap
Los pacientes llegan en cualquier orden, pero Entre varias ofertas de proveedores, procesas
se atiende primero al de mayor urgencia. La primero la mas barata. La prioridad es el
prioridad es el nivel de urgencia. precio (menor = mejor).
Cola de procesos del SO Dijkstra (rutas mas cortas)
max-heap min-heap
Windows o Linux deciden que proceso correr Google Maps, Waze. Para hallar el camino
proximo segun su nivel de prioridad. El mas corto, en cada paso se expande el nodo
sistema elige siempre el de mas prioridad. con la menor distancia acumulada.
Top-N (los N mejores) Compresion de Huffman
min-heap (tam. N) min-heap
Los 10 productos mas vendidos, las 5 noticias Para armar codigos compactos, en cada paso
mas leidas. Se guarda solo un heap de tamano se combinan los dos caracteres de menor
N y se compara con la raiz para decidir si frecuencia hasta formar el arbol final.
entra un nuevo elemento.
Tres formulas para movernos entre padre e hijos:
padre(i) = (i - 1) / 2
hijoIzq(i) = 2*i + 1
hijoDer(i) = 2*i + 2
El mismo heap visto como arreglo y como arbol — son la misma cosa:
ARREGLO (ASI VIVE EN MEMORIA) ARBOL (ASI SE PIENSA)
[0] [1] [2] [3] [4] [5]
9
9 4 6 1 3 5
4 6
1 3 5
[0] es la raiz (mayor prioridad). [1] y [2] son sus hijos. [3] y [4] son hijos de [1] . Y asi.
2. Insertar - algoritmo
Pones el elemento al final del arreglo y lo subes intercambiandolo con su padre mientras
compara(hijo, padre) sea verdadero (es decir, mientras el hijo deba ir antes que el padre).
void subir(int i) {
while (i > 0) { // mientras no sea la raiz
int padre = (i - 1) / 2;
if (compara(datos[i], datos[padre])) { // ¿tengo mas prioridad que
swap(datos[i], datos[padre]);
i = padre; // sigo subiendo
} else break; // ya estoy bien ubicado
}
}
void insertar(T elem) {
datos.push_back(elem); // agrego al final
subir([Link]() - 1); // y subo
}
Paso a paso
Insertar 9 en [6, 4, 5, 1, 3] (max-heap).
Inicial
[0] [1] [2] [3] [4]
6
6 4 5 1 3
6 4 5 1 3
4 5
1 3
Paso 1 - agrego 9 al final (posicion 5)
[0] [1] [2] [3] [4] [5]
6
6 4 5 1 3 9
4 5
1 3 9
padre(5) = (5-1)/2 = 2 → arr[2] = 5. Como 9 > 5, intercambio.
Paso 2 - 9 sube a posicion 2
[0] [1] [2] [3] [4] [5]
6
6 4 9 1 3 5
4 9
1 3 5
padre(2) = (2-1)/2 = 0 → arr[0] = 6. Como 9 > 6, intercambio.
Paso 3 - 9 llega a la raiz
[0] [1] [2] [3] [4] [5]
9
9 4 6 1 3 5
4 6
1 3 5
i = 0, no tiene padre. Listo.
3. Extraer - algoritmo
Extraer = sacar y devolver la raiz (el de mayor prioridad). Si llamas extraer varias veces,
sacas los elementos en orden.
Para no dejar un hueco arriba: mueves el ultimo del arreglo a la raiz y lo bajas
intercambiandolo con el hijo de mayor prioridad (segun el comparador), hasta que ningun
hijo lo supere.
¿Cual hijo elijo? El que el comparador prefiera. En max-heap es el mayor; en min-heap, el
menor. Por eso el codigo no decide eso a mano: deja que compara lo resuelva.
void bajar(int i) {
int n = [Link]();
while (true) {
int izq = 2*i + 1; // indices de los h
i t d 2 i 2
int der = 2*i + 2;
int mejor = i; // arranco asumiend
// ¿algun hijo tiene mas prioridad que el candidato actual?
if (izq < n && compara(datos[izq], datos[mejor])) mejor = izq;
if (der < n && compara(datos[der], datos[mejor])) mejor = der;
if (mejor == i) break; // ningun hijo me s
swap(datos[i], datos[mejor]);
i = mejor; // sigo bajando
}
}
T extraer() {
T tope = datos[0]; // la raiz se devue
datos[0] = [Link](); // el ultimo a la r
datos.pop_back();
if (![Link]()) bajar(0);
return tope;
}
Paso a paso
Extraer de [9, 4, 6, 1, 3, 5] (max-heap).
Inicial
[0] [1] [2] [3] [4] [5]
9
9 4 6 1 3 5
4 6
1 3 5
Paso 1 - guardo 9, muevo el ultimo (5) a la raiz
[0] [1] [2] [3] [4]
5
5 4 6 1 3
4 6
1 3
el 5 esta en la raiz [0]. Sus hijos estan en [1] (valor 4) y [2] (valor 6). Entre 4 y 6, el de mas prioridad
es 6. Como 5 < 6, intercambio.
Paso 2 - 5 baja a posicion 2
[0] [1] [2] [3] [4]
6
6 4 5 1 3
4 5
1 3
el 5 esta en la posicion [2]. Sus hijos estarian en las posiciones 2·2+1 = 5 y 2·2+2 = 6, pero el arreglo
solo llega hasta [4]. No tiene hijos, listo.
Resultado: extraido 9, nueva raiz 6
[0] [1] [2] [3] [4]
6
6 4 5 1 3
4 5
1 3