Un montículo tiene siempre el menor a mano
Un montículo (heap en inglés) es un árbol guardado en una lista que mantiene el elemento menor siempre en la primera posición. Sirve para hacer una cola de prioridad: sacar siempre lo más urgente, sin ordenar todo cada vez.
Una impresora de oficina atiende primero el trabajo más urgente, aunque haya llegado el último.
Al final de esta lección
Nota
Puedo mantener el elemento menor a mano con un montículo.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Montículo | un árbol donde cada padre es menor que sus hijos |
| Cola de prioridad | una cola donde sale primero lo más urgente |
| Subir | cambiar un nodo con su padre mientras sea menor |
| Bajar | cambiar un nodo con su hijo menor mientras sea mayor |
| Padre e hijo | un nodo y los dos nodos que cuelgan de él |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Regla del montículo: el padre no es mayor
En un montículo mínimo, cada nodo es menor o igual que sus dos hijos. No importa cuál de los hijos es mayor.
Por esa regla, el menor de todos está siempre arriba, en la raíz. No hace falta buscarlo: se lee en un paso.
Un montículo cabe en una lista
Un montículo no necesita nodos con enlaces. Se guarda en una lista, nivel a nivel, de arriba abajo y de izquierda a derecha.
Los hijos de la posición i están en 2 * i + 1 y 2 * i + 2. El padre de i está en (i - 1) // 2, la división entera.
El montículo en una lista
| Posición | Valor | Su padre |
|---|---|---|
| 0 | 1 | Ninguno: es la raíz |
| 1 | 3 | Posición 0 (valor 1) |
| 2 | 8 | Posición 0 (valor 1) |
| 3 | 5 | Posición 1 (valor 3) |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Añadir: entra por el final y sube
Para añadir un valor lo pones al final de la lista. Puede romper la regla, así que lo comparas con su padre: si es menor, se cambian.
Repites hasta que el padre sea menor o llegues a la raíz. Como el árbol tiene pocos niveles, subir cuesta pocos pasos.
Añadir números a un montículo
# Un montículo mínimo en una lista: el padre de la posición i está en (i - 1) // 2.
heap = []
for number in [5, 3, 8, 1]:
heap.append(number) # entra por el final
i = len(heap) - 1
while i > 0:
parent = (i - 1) // 2
if heap[i] < heap[parent]:
heap[i], heap[parent] = heap[parent], heap[i] # sube un nivel
i = parent
else:
break
print(heap)
# Añade el 2 al final de la lista de números y mira cómo sube.
Añadir cuatro números paso a paso
| Se añade | Se compara con | La lista queda |
|---|---|---|
| 5 | Nada: es la raíz | [5] |
| 3 | Su padre 5: es menor, se cambian | [3, 5] |
| 8 | Su padre 3: es mayor, se queda | [3, 5, 8] |
| 1 | El padre 5 y luego el 3: sube dos veces | [1, 3, 8, 5] |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un montículo con heapq
python3 -c "import heapq; h = [5, 3, 8, 1]; heapq.heapify(h); print(h)"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Sacar el menor: el último ocupa su sitio
Para sacar el menor, lo guardas, llevas el último elemento de la lista a la raíz y lo haces bajar.
En cada paso lo comparas con su hijo menor: si es mayor que él, se cambian. Paras cuando es menor que sus hijos o cuando no tiene. La regla vuelve a cumplirse.
Sacar tres veces el menor
python3 -c "import heapq; h = [5, 3, 8, 1]; heapq.heapify(h); print(heapq.heappop(h), heapq.heappop(h), heapq.heappop(h))"Se muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Un error frecuente
Advertencia
Mucha gente cree que la lista de un montículo está ordenada. No lo está: solo el primer elemento es el menor. Fíjate en [1, 3, 8, 5]: el 8 va antes que el 5. Para sacar los valores ordenados, hay que sacar el menor una y otra vez.
Para ir más lejos
Con un montículo ordenas una lista: añades todos los valores y los sacas uno a uno. Escríbelo y cuenta cuántas comparaciones haces con diez valores.
Compara con una lista ordenada a mano al insertar cada valor, como en la primera lección.