Heapify, push y pop desde cero
Implemente heapify-up para push y heapify-down para pop y construya después un heap a partir de un array sin ordenar en O(n) mediante el algoritmo de Floyd.
Heapify, push y pop desde cero es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Construir una clase MinHeap
Implementar un heap desde cero demuestra el dominio de sus mecanismos internos y ocasionalmente se solicita en entrevistas para puestos sénior. Una clase MinHeap encapsula un array y expone las operaciones push, pop, peek y size. Internamente mantiene la propiedad de heap llamando a sift-up después de push y a sift-down después de pop. Comprender esta implementación hace que el módulo heapq de Python resulte completamente transparente.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
def pop(self):
if len(self._data) == 1:
return self._data.pop()
min_val = self._data[0]
self._data[0] = self._data.pop() # move last to root
self._sift_down(0)
return min_val
def peek(self):
return self._data[0] if self._data else None
def size(self):
return len(self._data)
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
print('MinHeap class skeleton defined')Implementar sift-up
Sift-up compara un nodo con su padre y lo intercambia hacia arriba mientras se infrinja la propiedad de heap (parent <= child en un min-heap). La clave es que el elemento recién insertado se encuentra al final y asciende hasta su posición correcta. El bucle while se ejecuta como máximo floor(log n) veces, que es la altura del árbol. Asigne i = parent en cada paso para continuar avanzando hacia arriba.
class MinHeap:
def __init__(self):
self._data = []
def _parent(self, i): return (i - 1) // 2
def _left(self, i): return 2 * i + 1
def _right(self, i): return 2 * i + 2
def _sift_up(self, i):
while i > 0:
p = self._parent(i)
if self._data[p] > self._data[i]: # parent > child: swap
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else:
break # heap property satisfied
def push(self, val):
self._data.append(val)
self._sift_up(len(self._data) - 1)
h = MinHeap()
for v in [5, 3, 8, 1, 4]:
h.push(v)
print(h._data) # valid min-heapImplementar sift-down
Sift-down desplaza un nodo hacia abajo intercambiándolo repetidamente con su hijo menor (en un min-heap), hasta que ninguno de los hijos sea menor o el nodo llegue a una hoja. Compare siempre con ambos hijos e intercambie el nodo con el menor para mantener la propiedad de heap. Recuerde comprobar que los índices de los hijos estén dentro de los límites antes de comparar los valores.
def _sift_down(data, i):
n = len(data)
while True:
smallest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and data[l] < data[smallest]:
smallest = l
if r < n and data[r] < data[smallest]:
smallest = r
if smallest == i:
break # already the smallest among i, l, r
data[i], data[smallest] = data[smallest], data[i]
i = smallest
# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap) # 1 should reach top, 10 sinkCompletar MinHeap con pop
La operación pop elimina y devuelve la raíz (el mínimo en un min-heap). Para mantener la forma de árbol binario completo, mueva el último elemento a la posición de la raíz y, después, aplique sift-down. Así se evita crear huecos en el array y se mantiene válida la representación. Caso límite: si solo queda un elemento, extráigalo y devuélvalo directamente sin aplicar sift-down.
class MinHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] > self._data[i]:
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop() # last -> root
i, n = 0, len(self._data)
while True:
s, l, r = i, 2*i+1, 2*i+2
if l < n and self._data[l] < self._data[s]: s = l
if r < n and self._data[r] < self._data[s]: s = r
if s == i: break
self._data[i], self._data[s] = self._data[s], self._data[i]
i = s
return result
h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [1,2,3,4,5,8] sortedAlgoritmo de heapify de Floyd
El algoritmo de Floyd construye un min-heap a partir de un array sin ordenar en O(n), llamando a sift-down para cada nodo que no sea hoja, empezando por el último nodo interno (n//2 - 1) y avanzando hacia la raíz. Las hojas ya son heaps válidos de un solo elemento. El límite de tiempo O(n) se debe a que la mayoría de los nodos están cerca de la parte inferior del árbol y solo necesitan descender una distancia pequeña.
def heapify(arr):
n = len(arr)
# Start from last non-leaf: index n//2 - 1
# Work backward to root (index 0)
for i in range(n // 2 - 1, -1, -1):
# Sift down node at index i
j = i
while True:
s = j
l, r = 2*j+1, 2*j+2
if l < n and arr[l] < arr[s]: s = l
if r < n and arr[r] < arr[s]: s = r
if s == j: break
arr[j], arr[s] = arr[s], arr[j]
j = s
return arr
arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr) # arr[0] should be 1Por qué el algoritmo de Floyd es O(n)
La demostración de O(n): el árbol tiene n/2^(k+1) nodos a altura k. Cada nodo a altura k realiza como máximo k intercambios durante sift-down. Trabajo total = suma para todas las alturas k: n/2^(k+1) * k. Esta serie geométrica converge a O(n). En contraste, la inserción ingenua uno a uno requiere O(log n) por cada push, por lo que n pushes cuestan O(n log n). El algoritmo de Floyd es estrictamente mejor para construir heaps por lotes.
import time
import random
# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1)) # reverse sorted = worst case for push
# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
j = i
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n and data1[l] < data1[s]: s = l
if r < n and data1[r] < data1[s]: s = r
if s == j: break
data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')
# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')Insertar en un heap de una colección existente
heapq.heappushpop y heapq.heapreplace de Python son operaciones combinadas eficientes. heappushpop(heap, item) inserta el elemento nuevo y extrae inmediatamente el menor, lo que resulta más eficiente que realizar dos llamadas independientes. heapreplace(heap, item) extrae el menor e inserta el elemento nuevo en una sola pasada (para que sea correcto, el elemento nuevo debe ser >= que el mínimo anterior). Estas operaciones son útiles en algoritmos de streaming de los k mejores elementos.
import heapq
heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)
# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)
# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)
# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard patternImplementar un MaxHeap desde cero
Un MaxHeap invierte la comparación: el padre debe ser mayor o igual que todos sus descendientes. Simplemente invierta la comparación en sift-up y sift-down. Como alternativa, encapsule los valores en una clase de negación o niegue los enteros, como se hace con el heapq de Python. Implementarlo desde cero demuestra que los min-heaps y max-heaps son estructuras idénticas en las que solo cambia el operador de comparación.
class MaxHeap:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
i = len(self._data) - 1
while i > 0:
p = (i - 1) // 2
if self._data[p] < self._data[i]: # FLIP: parent < child = violation
self._data[p], self._data[i] = self._data[i], self._data[p]
i = p
else: break
def pop(self):
if not self._data: return None
if len(self._data) == 1: return self._data.pop()
result = self._data[0]
self._data[0] = self._data.pop()
i, n = 0, len(self._data)
while True:
g = i; l, r = 2*i+1, 2*i+2
if l < n and self._data[l] > self._data[g]: g = l # FLIP
if r < n and self._data[r] > self._data[g]: g = r # FLIP
if g == i: break
self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
return result
h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)]) # [8,5,4,3,2,1]Eliminar un elemento arbitrario de un heap
Eliminar un elemento arbitrario (que no sea la raíz) de un heap requiere O(log n), pero es necesario conocer el índice del elemento. Sustituya el elemento por el último, elimine este último y, después, aplique sift-up o sift-down al elemento de reemplazo (solo una de las dos direcciones infringirá la propiedad de heap). Esta técnica se utiliza en el algoritmo de Dijkstra con eliminación diferida y en colas de prioridad compatibles con operaciones decrease-key.
def delete_at_index(heap, i):
n = len(heap)
heap[i] = heap[n - 1]
heap.pop()
if i >= len(heap):
return # deleted the last element
# Try sift-up first
p = (i - 1) // 2
if i > 0 and heap[i] < heap[p]:
while i > 0:
p = (i - 1) // 2
if heap[p] > heap[i]:
heap[p], heap[i] = heap[i], heap[p]; i = p
else: break
else: # sift down
j = i; n2 = len(heap)
while True:
s = j; l, r = 2*j+1, 2*j+2
if l < n2 and heap[l] < heap[s]: s = l
if r < n2 and heap[r] < heap[s]: s = r
if s == j: break
heap[j], heap[s] = heap[s], heap[j]; j = s
heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2) # delete element at index 2 (value=2)
print('After:', heap) # 2 removed, heap still validHeap para los elementos más frecuentes
Top-K Frequent Elements (LeetCode #347) utiliza un min-heap de tamaño k. Mantenga un min-heap en el que cada entrada sea (frequency, element). Procese cada elemento distinto: si el heap tiene menos de k elementos, haga push; de lo contrario, si la frecuencia del elemento nuevo supera el mínimo del heap, haga pop y push. El heap final contiene los k elementos más frecuentes en un tiempo de O(n log k).
import heapq
from collections import Counter
def top_k_frequent(nums, k):
count = Counter(nums)
# Min-heap of (frequency, num)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap) # remove least frequent
return [num for freq, num in heap]
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]Aplicaciones de los heaps en la planificación
Más allá de la programación competitiva, los heaps impulsan sistemas de planificación reales. Los planificadores de tareas de los sistemas operativos utilizan una cola de prioridad (heap) para ejecutar siempre el proceso listo con mayor prioridad. Las simulaciones dirigidas por eventos procesan los eventos en orden temporal mediante un min-heap cuya clave es el instante del evento. Los planificadores de paquetes de red priorizan el tráfico según la clase de calidad de servicio. Comprender el heap le proporciona un modelo mental para todos estos sistemas y resulta útil de forma natural en las entrevistas de diseño de sistemas sobre colas y planificación.
import heapq
# Simple event-driven simulation using a heap
events = [] # (time, event_description)
def schedule(time, event):
heapq.heappush(events, (time, event))
def process_next():
time, event = heapq.heappop(events)
print(f't={time}: {event}')
return time, event
# Schedule events out of order:
schedule(10, 'Send email')
schedule(3, 'Open app')
schedule(7, 'Process request')
schedule(1, 'Start server')
# Process in time order:
while events:
process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time orderComprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección ha aprendido: MinHeap y MaxHeap desde cero con sift-up y sift-down, el algoritmo heapify O(n) de Floyd y por qué supera a la inserción individual O(n log n), además de aplicaciones prácticas, como encontrar los elementos más frecuentes de tipo top-k y delete-at-index. A continuación, explorará el módulo heapq de Python y las técnicas para simular un max-heap.
Preguntas frecuentes
¿La lección «Heapify, push y pop desde cero» es gratis?
Sí — el texto completo de «Heapify, push y pop desde cero» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Heapify, push y pop desde cero»?
Implemente heapify-up para push y heapify-down para pop y construya después un heap a partir de un array sin ordenar en O(n) mediante el algoritmo de Floyd. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Heapify, push y pop desde cero»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Propiedad del heap y representación en array
- Heapify, push y pop desde cero
- heapq de Python y trucos para max-heap
- Mediana de un flujo de datos y combinación k-way