Fundamentos del heap
Paso 1 de 25
Cuatro pujas en un array simple. Leído como árbol, el índice i es padre de 2i+1 y 2i+2: esa aritmética es el árbol.
La idea
Un heap (montículo) es un árbol binario completo donde cada padre le gana a sus hijos: en un min-heap, es más pequeño. Es una promesa mucho más débil que el ordenamiento (sorting), y mucho más barata de mantener.
Solo la raíz está garantizada. Push y pop cuestan O(log n); ver al ganador con peek cuesta O(1). El árbol vive en un array (arreglo) común: el nodo i tiene hijos en 2i + 1 y 2i + 2.
Ejemplo del mundo real
El tablero de pujas de una casa de subastas solo muestra la oferta más alta del momento. Nadie mantiene un ranking completo de cada puja gritada: ese trabajo se desperdiciaría, porque solo la de arriba puede ganar. Una puja nueva o se queda con el tablero o desaparece en silencio entre las demás.
El código
Te toca
¿Qué imprime esto?
import heapq
h = [5, 8, 2]
heapq.heapify(h)
heapq.heappush(h, 4)
print(heapq.heappop(h), heapq.heappop(h))Mini quiz
1 / 3