O básico de heaps
Passo 1 de 25
Quatro lances num array simples. Lido como árvore, o índice i é pai de 2i+1 e 2i+2: essa aritmética é a árvore.
A ideia
Um heap é uma árvore binária completa em que todo pai vence os filhos — no min-heap, sendo menor. É uma promessa bem mais fraca que a ordenação, e bem mais barata de manter.
Só a raiz é garantida. Inserir (push) e remover (pop) custam O(log n); consultar o vencedor custa O(1). A árvore mora em um array comum: o nó i tem filhos em 2i + 1 e 2i + 2.
Exemplo do mundo real
O painel de lances de uma casa de leilões só mostra a maior oferta atual. Ninguém mantém um ranking de todos os lances já gritados — seria trabalho perdido, porque só o maior pode vencer. Um lance novo ou toma o painel ou some em silêncio entre os demais.
O código
Sua vez
O que isto imprime?
import heapq
h = [5, 8, 2]
heapq.heapify(h)
heapq.heappush(h, 4)
print(heapq.heappop(h), heapq.heappop(h))Mini quiz
1 / 3