Heapify, Push e Pop do Zero
Implemente heapify para cima no push e heapify para baixo no pop e construa um heap a partir de um array não ordenado em O(n) usando o algoritmo de Floyd.
Heapify, Push e Pop do Zero é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Construção de uma classe MinHeap
Implementar um montículo do zero demonstra domínio dos mecanismos subjacentes e às vezes é uma exigência em entrevistas para cargos seniores. Uma classe MinHeap encapsula um vetor e expõe as operações push, pop, peek e size. Internamente, ela mantém a propriedade do montículo chamando a restauração para cima após push e a restauração para baixo após pop. Entender essa implementação torna o módulo heapq do Python 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')Implementação da restauração para cima
A restauração para cima compara um nó com seu parent e faz trocas para cima enquanto a propriedade do montículo (parent <= filho para montículo mínimo) for violada. O ponto principal é que o elemento recém-inserido está no final e sobe até sua posição correta. O laço de repetição executa no máximo floor(log n) vezes — a altura da árvore. Atribua i = parent a cada etapa para continuar subindo.
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-heapImplementação da restauração para baixo
A restauração para baixo empurra um nó para baixo trocando-o repetidamente com seu filho menor (no montículo mínimo), até que nenhum dos filhos seja menor ou o nó alcance uma folha. Compare sempre com ambos os filhos e troque com o menor para manter a propriedade do montículo. Lembre-se de verificar se os índices dos filhos estão dentro dos limites antes de comparar os 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 sinkCompletando o MinHeap com pop
A operação pop remove e retorna a raiz (o mínimo em um montículo mínimo). Para manter o formato de árvore binária completa, mova o último elemento para a posição da raiz e, em seguida, aplique a restauração para baixo. Isso evita criar lacunas no vetor e mantém a representação válida. Caso extremo: se restar apenas um elemento, faça pop e retorne-o diretamente, sem restauração para baixo.
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 heapify de Floyd
O algoritmo heapify de Floyd constrói um montículo mínimo a partir de um vetor não ordenado em O(n), chamando a restauração para baixo em cada nó não folha, começando pelo último nó interno (n//2 - 1) e avançando em direção à raiz. As folhas já são montículos válidos triviais de um elemento. O limite de O(n) time vem do fato de que a maioria dos nós está próxima da parte inferior da árvore e só precisa descer uma pequena distância.
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 que o algoritmo de Floyd é O(n)
A prova de O(n): a árvore tem n/2^(k+1) nós na altura k. Cada nó na altura k realiza no máximo k trocas durante a restauração para baixo. Trabalho total = soma sobre todas as alturas k: n/2^(k+1) * k. Essa série geométrica converge para O(n). Compare com a inserção ingênua, um elemento por vez: cada push custa O(log n), portanto n pushes custam O(n log n). O algoritmo de Floyd é estritamente melhor para a construção em lote.
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')Inserção com push em uma coleção existente
heapq.heappushpop e heapq.heapreplace do Python são operações combinadas eficientes. heappushpop(heap, item) insere o novo item e imediatamente remove o menor — é mais eficiente do que duas chamadas separadas. heapreplace(heap, item) remove o menor e insere o novo item em uma única passagem (para estar correto, o novo item deve ser >= ao mínimo anterior). Essas operações são úteis em algoritmos de fluxo dos k primeiros.
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 patternImplementação de um MaxHeap do zero
Um MaxHeap inverte a comparação: o parent deve ser maior ou igual a todos os descendentes. Basta inverter a comparação na restauração para cima e na restauração para baixo. Como alternativa, envolva os valores em uma classe de negação ou negue os inteiros, como é feito com o heapq do Python. Implementar do zero demonstra que os montículos mínimos e máximos têm estruturas idênticas, mudando apenas o operador de comparação.
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]Excluir um elemento arbitrário de um montículo
Excluir um elemento arbitrário (que não seja a raiz) de um montículo custa O(log n), mas exige conhecer o índice do elemento. Substitua o elemento pelo último, remova o último e, em seguida, aplique a restauração para cima ou para baixo ao substituto (apenas uma direção violará a propriedade do montículo). Essa técnica é usada no algoritmo de Dijkstra com exclusão preguiçosa e em filas de prioridade que oferecem operações de redução de chave.
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 validMontículo para elementos mais frequentes entre os K primeiros
Elementos mais frequentes entre os K primeiros (LeetCode #347) usa um montículo mínimo de tamanho k. Mantenha um montículo mínimo em que cada entrada seja (frequency, element). Processe cada elemento exclusivo: se o montículo tiver menos de k elementos, faça push; caso contrário, se a frequência do novo elemento exceder o mínimo do montículo, faça pop e push. O montículo final contém os k elementos mais frequentes em O(n log k) time.
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]Aplicações de montes no escalonamento
Além da programação competitiva, os montes são fundamentais para sistemas de escalonamento do mundo real. Os escalonadores de tarefas dos sistemas operacionais usam uma fila de prioridade (monte) para sempre executar o processo pronto de maior prioridade. Simulações orientadas a eventos processam os eventos em ordem de tempo usando um monte mínimo ordenado pelo horário do evento. Os escalonadores de pacotes de rede priorizam o tráfego por classe de qualidade de serviço. Compreender o monte fornece um modelo mental para todos esses sistemas e surge naturalmente em entrevistas de projeto de sistemas sobre enfileiramento e escalonamento.
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 orderVerificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: MinHeap e MaxHeap do zero, com subida e descida no monte; o algoritmo heapify de Floyd, O(n), e por que ele supera a inserção individual em O(n log n); além de aplicações práticas, incluindo elementos frequentes entre os k primeiros e exclusão por índice. Em seguida, exploraremos o módulo heapq do Python e técnicas para montes máximos.
Perguntas Frequentes
A aula “Heapify, Push e Pop do Zero” é grátis?
Sim — o texto completo de “Heapify, Push e Pop do Zero” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Heapify, Push e Pop do Zero”?
Implemente heapify para cima no push e heapify para baixo no pop e construa um heap a partir de um array não ordenado em O(n) usando o algoritmo de Floyd. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.
Quanto tempo leva a aula “Heapify, Push e Pop do Zero”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Propriedade de Heap e Representação em Array
- Heapify, Push e Pop do Zero
- heapq do Python e Técnicas de Max-Heap
- Mediana de um Fluxo de Dados e Intercalação em K Vias