Colas en Python - Heaps (Min-Heap y Max-Heap)

9.1 Visión general

Los heaps son árboles binarios completos que mantienen la propiedad de orden parcial: cada nodo es mayor o igual que sus hijos (max-heap) o menor o igual (min-heap). Gracias a esta propiedad, permiten acceder rápidamente al elemento de mayor o menor prioridad y son la base de las colas de prioridad eficientes.

En Python se representan sobre listas y se manejan con el módulo heapq, que opera con complejidad logarítmica para insertar o extraer.

9.2 Terminología esencial

Árbol completo: todas las capas están llenas, salvo posiblemente la última, que se completa de izquierda a derecha.
Raíz: nodo en la posición cero del arreglo; contiene el valor extremo según el tipo de heap.
Heap property: cada padre respeta la relación ordenada con sus hijos directos. No garantiza orden total.

Conocer estos términos agiliza la lectura de los algoritmos de heapify e inserción.

9.3 Representación en un array

La lista almacena el heap nivel por nivel. A partir de un índice i se calculan sus vecinos sin punteros adicionales:

Padre: (i - 1) / 2 (truncando decimales).
Hijo izquierdo: 2 * i + 1.
Hijo derecho: 2 * i + 2.

Esta representación es compacta y permite reducir el uso de memoria respecto a las listas enlazadas.

9.4 Operaciones principales

En ambos heaps las operaciones fundamentales son heappush e heappop. heapq implementa min-heap por defecto; para simular un max-heap se suele invertir el signo de la prioridad.

import heapq

# Min-heap
h = []
heapq.heappush(h, 45)
heapq.heappush(h, 10)
heapq.heappush(h, 78)
heapq.heappush(h, 32)

print("Heap interno:", h)

while h:
  print("extraido:", heapq.heappop(h))

# Max-heap usando prioridades negativas
max_heap = []
heapq.heappush(max_heap, -45)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -78)
heapq.heappush(max_heap, -32)

print("Max-heap interno:", max_heap)
while max_heap:
  print("extraido max:", -heapq.heappop(max_heap))

Ambas operaciones mantienen la complejidad O(log n). Para un max-heap se invierte el signo de las prioridades o se envuelven los valores en una tupla con prioridad negativa.

9.5 Min-Heap vs Max-Heap

Los heaps pueden invertirse con una sola condición de comparación o utilizando un factor signo que se multiplica por cada valor. Elegir uno u otro depende del problema: Dijkstra requiere min-heap, mientras que un planificador que atiende prioridades altas usa max-heap.

En implementaciones genéricas se recibe un puntero a función comparadora para que el usuario decida la relación de orden.

9.6 Heapify y construcción masiva

Cuando se parte de una lista arbitraria es más eficiente aplicar heapify de abajo hacia arriba que insertar elemento por elemento. El siguiente algoritmo transforma la lista en O(n):

import heapq

datos = [5, 1, 9, 4, 2, 7]
heapq.heapify(datos)  # convierte la lista en min-heap in-place
print("Heapificado:", datos)

Solo los nodos internos (hasta n/2) requieren reposicionarse porque los nodos hoja ya cumplen la propiedad del heap.

9.7 Heapsort en dos pasos

Heapsort construye un heap y luego extrae repetidamente para generar una secuencia ordenada. En Python puedes apoyarte en heapq o usar una aproximación simple:

import heapq

def heapsort(iterable):
  h = list(iterable)
  heapq.heapify(h)
  return [heapq.heappop(h) for _ in range(len(h))]


print(heapsort([9, 1, 5, 3, 8, 2]))  # [1, 2, 3, 5, 8, 9]

La complejidad es O(n log n) y no necesita memoria auxiliar distinta de la lista heapificada.

9.8 Ejemplo completo en Python

El siguiente programa crea un max-heap a partir de un min-heap invirtiendo las prioridades, inserta valores, extrae todos y luego demuestra cómo heapify acelera la construcción:

import heapq


class MaxHeap:
  def __init__(self):
    self._heap = []
    self._contador = 0

  def push(self, valor):
    heapq.heappush(self._heap, (-valor, self._contador, valor))
    self._contador += 1

  def pop(self):
    if not self._heap:
      return None
    _, _, valor = heapq.heappop(self._heap)
    return valor

  def heapify(self, valores):
    self._heap = [(-v, i, v) for i, v in enumerate(valores)]
    heapq.heapify(self._heap)
    self._contador = len(valores)

  def imprimir(self):
    print("[heap] n=", len(self._heap), "->", [v for _, _, v in self._heap])


if __name__ == "__main__":
  heap = MaxHeap()

  for v in (45, 10, 78, 32):
    heap.push(v)
  heap.imprimir()

  while len(heap._heap):
    print("extraido:", heap.pop())
  heap.imprimir()

  heap.heapify([5, 1, 9, 4, 2, 7])
  heap.imprimir()

Ejecutar en el editor online

Integra las versiones completas de inserción, extracción y heapify para ejecutar el ejemplo. Observa cómo los valores se devuelven en orden descendente a pesar de haberse cargado en desorden.

Retornar

9 - Heaps (Min-Heap y Max-Heap)