Pular para o conteúdo

O básico de heaps

Aula 1 de 7 · 5 min

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

Em um min-heap, o que é garantido sobre o valor no índice 0?