Heaps (Max-Heap) — do conceito à fila de prioridade (com corretude e Big-O)

Invariantes, operações, heapsort e fila de prioridade com desempate FIFO

Por Fábio Linhares • Estruturas de Dados e Algoritmos (Heaps)

Visão geral e competências

Este conjunto de questões não é para decorar heap. É para aprender a pensar com heap: modelar o problema, justificar corretude, estimar custo e validar por evidência.

A progressão vai de fundamentos (árvore completa, ordem parcial, representação em array) até engenharia (fila de prioridade para triagem com desempate FIFO e decisão entre heap vs array ordenado).

Critério de saída: explicar com clareza qual é o invariante, por que as operações preservam/recuperam a propriedade, qual é o custo e quais casos-limite podem quebrar a solução.

Em heap, todos os níveis são completos, exceto possivelmente o último; e no último os nós são preenchidos da esquerda para a direita, sem buracos.

Essa forma fixa permite representar a árvore em array sem ponteiros, com relações por índice: pai (i-1)//2, filhos 2i+1 e 2i+2.

Pro tip: Em dúvida, desenhe níveis e confirme preenchimento contínuo da esquerda para a direita no último nível.

Heap não é BST. Em max-heap, a garantia é local: cada pai tem prioridade maior ou igual à dos filhos.

Por isso ele é parcialmente ordenado: a raiz é o maior, mas não existe ordem global entre irmãos ou entre subárvores.

Pro tip: Heap responde rápido quem é o maior agora; BST é melhor para buscar valores por ordem global.

Insere no fim do array (preserva árvore completa).
Aplica sift-up: enquanto o nó for maior que o pai, troca.
Para ao chegar na raiz ou quando o pai já for maior/igual.

Cada troca corrige uma violação local no caminho até a raiz. A altura do heap é O(log N), então o custo é O(log N).

Pro tip: A prova de corretude está na sequência de correções locais em um único caminho.

Critério: para todo índice pai i, vale key(a[i]) >= key(a[filho]) para cada filho existente.

def eh_heap(a, key=lambda x: x):
    """
    Retorna True se o array 'a' pode representar um max-heap segundo a função 'key'.
    """
    n = len(a)
    for i in range(n):
        l = 2*i + 1
        r = 2*i + 2
        if l < n and key(a[i]) < key(a[l]):
            return False
        if r < n and key(a[i]) < key(a[r]):
            return False
    return True

# testes rápidos
assert eh_heap([10, 9, 8, 6, 5, 7, 4, 2, 1, 3])
assert not eh_heap([9, 10])  # pai menor que filho

Pro tip: Primeiro garanta corretude; depois, se quiser, varra só até o último pai.

Tempo: O(N). O loop visita cada índice uma vez, com verificações O(1).

Memória extra: O(1), fora o array de entrada.

Pro tip: Sempre conecte número de iterações com custo por iteração.

Se items já for heap válido, copia direto. Caso contrário, insere item a item para preservar propriedade.

class Heap:
    """
    Max-heap baseado em array, com função de prioridade 'key'.
    """
    def __init__(self, items=None, key=lambda x: x):
        self._key = key
        self._a = []

        if items is None:
            return

        # Se já representa heap, copia (O(N)).
        if eh_heap(items, key=self._key):
            self._a = list(items)
        else:
            # Caso contrário, insere um a um (O(N log N)).
            for it in items:
                self.push(it)

    def __len__(self):
        return len(self._a)

    def peek(self):
        if not self._a:
            raise IndexError("heap vazio")
        return self._a[0]

    def push(self, x):
        self._a.append(x)
        self._sift_up(len(self._a) - 1)

    def pop(self):
        if not self._a:
            raise IndexError("heap vazio")
        root = self._a[0]
        last = self._a.pop()
        if self._a:
            self._a[0] = last
            self._sift_down(0)
        return root

    def _sift_up(self, i):
        a, key = self._a, self._key
        while i > 0:
            p = (i - 1) // 2
            if key(a[p]) >= key(a[i]):
                break
            a[p], a[i] = a[i], a[p]
            i = p

    def _sift_down(self, i):
        a, key = self._a, self._key
        n = len(a)
        while True:
            l = 2*i + 1
            r = 2*i + 2
            if l >= n:
                break
            j = l
            if r < n and key(a[r]) > key(a[l]):
                j = r
            if key(a[i]) >= key(a[j]):
                break
            a[i], a[j] = a[j], a[i]
            i = j

    def to_array(self):
        return list(self._a)

    def niveis(self):
        """
        Retorna o número de níveis do heap em O(log N):
        caminha sempre pelo filho esquerdo até sair do array.
        """
        n = len(self._a)
        if n == 0:
            return 0
        levels = 0
        i = 0
        while i < n:
            levels += 1
            i = 2*i + 1
        return levels

Pro tip: Em pop(), trate corretamente heap com 1 elemento.

Array da figura (ordem por níveis): [10, 9, 8, 6, 5, 7, 4, 2, 1, 3].

Como já é um heap válido, o construtor pode copiar diretamente.

h = Heap([10, 9, 8, 6, 5, 7, 4, 2, 1, 3])
assert h.to_array() == [10, 9, 8, 6, 5, 7, 4, 2, 1, 3]

Pro tip: Em heap, array já está em level-order naturalmente.

Após push(11), o heap fica: [11, 10, 8, 6, 9, 7, 4, 2, 1, 3, 5].

h = Heap([10, 9, 8, 6, 5, 7, 4, 2, 1, 3])
h.push(11)
assert h.to_array() == [11, 10, 8, 6, 9, 7, 4, 2, 1, 3, 5]

Pro tip: O novo item entra no fim; depois sobe apenas pelo caminho dos pais.

Removendo a raiz (10), o heap atualizado fica: [9, 6, 8, 3, 5, 7, 4, 2, 1].

h = Heap([10, 9, 8, 6, 5, 7, 4, 2, 1, 3])
raiz = h.pop()
assert raiz == 10
assert h.to_array() == [9, 6, 8, 3, 5, 7, 4, 2, 1]

Pro tip: Em max-heap, no sift-down sempre compare com o maior filho.

Inserções: 46, 13, 25, 1, 3, 90, 59.

Ordem de remoção em max-heap: [90, 59, 46, 25, 13, 3, 1].

Pro tip: Remover todos os elementos de um heap é o raciocínio-base do heapsort.

Versão conceitual: constrói heap e extrai raízes para um array de saída.

Versão in-place com max-heap: heapify, troca raiz com fim, reduz heap ativo e faz sift-down na raiz, repetindo até ordenar.

Com max-heap, extração direta gera ordem decrescente; para crescente use min-heap ou preencha de trás para frente.

Pro tip: Heapsort in-place combina seleção do máximo com manutenção do heap no próprio array.

Heapsort tem pior caso O(N log N).

Construção do heap: O(N) (heapify/Floyd) ou O(N log N) por inserções repetidas.
Extrações: N remoções de O(log N), totalizando O(N log N).
Memória extra: O(1) na versão in-place.

Comparação típica: Bubble/Insertion/Selection O(N²); Merge O(N log N) com memória extra; Quick com média O(N log N) e pior caso O(N²).

Heapsort não é estável como ordenação, mas oferece pior caso garantido em O(N log N).

Pro tip: Quando requisito é pior caso garantido, heapsort costuma entrar como opção conservadora.

Para contar níveis, caminhe sempre para o filho esquerdo (2i+1) até sair do array. Cada passo desce um nível.

assert Heap([]).niveis() == 0
assert Heap([10]).niveis() == 1
assert Heap([10, 9]).niveis() == 2
assert Heap([10, 9, 8, 7]).niveis() == 3

Pro tip: Em árvore completa, a altura cresce em ordem de log N.

Regra: maior gravidade primeiro; em empate, menor seq primeiro. Em max-heap, use chave (gravidade, -seq).

class EmergencyQueueHeap:
    def __init__(self):
        self._heap = Heap(key=lambda p: (p["gravidade"], -p["seq"]))

    def enqueue(self, paciente: dict):
        self._heap.push(paciente)

    def dequeue(self) -> dict:
        return self._heap.pop()

    def __len__(self):
        return len(self._heap)

# exemplo
fila = EmergencyQueueHeap()
pacientes = [
    {"seq": 1, "nome": "José",  "gravidade": 2},
    {"seq": 2, "nome": "Márcia","gravidade": 3},
    {"seq": 3, "nome": "André", "gravidade": 2},
    {"seq": 4, "nome": "Bruna", "gravidade": 5},
    {"seq": 5, "nome": "Caio",  "gravidade": 5},
]
for p in pacientes:
    fila.enqueue(p)

assert fila.dequeue()["nome"] == "Bruna"
assert fila.dequeue()["nome"] == "Caio"
assert fila.dequeue()["nome"] == "Márcia"
assert fila.dequeue()["nome"] == "José"
assert fila.dequeue()["nome"] == "André"

Pro tip: Encode a regra de negócio na chave de prioridade, não em condicionais espalhadas.

Mantenha lista ordenada por prioridade e remova do final com pop() para ter remoção O(1). Inserção segue O(N) por deslocamentos.

Observação: esta abordagem assume chave totalmente ordenável. No exemplo, seq deve ser único para evitar empate completo de prioridade.

import bisect

class EmergencyQueueSortedArray:
    def __init__(self):
        self._a = []  # guarda tuplas (prioridade, paciente)

    def _prio(self, p):
        return (p["gravidade"], -p["seq"])

    def enqueue(self, paciente: dict):
        item = (self._prio(paciente), paciente)
        # mantém em ordem crescente; maior prioridade fica no final
        bisect.insort(self._a, item)

    def dequeue(self) -> dict:
        if not self._a:
            raise IndexError("fila vazia")
        return self._a.pop()[1]

    def __len__(self):
        return len(self._a)

fila = EmergencyQueueSortedArray()
for p in pacientes:
    fila.enqueue(p)

assert fila.dequeue()["nome"] == "Bruna"
assert fila.dequeue()["nome"] == "Caio"
assert fila.dequeue()["nome"] == "Márcia"

Pro tip: bisect acha rápido a posição, mas inserir em array desloca elementos.

Heap: enqueue O(log N), dequeue O(log N).

Array ordenado: busca de posição pode ser O(log N), mas inserção desloca elementos e custa O(N); dequeue no final é O(1).

Em triagem hospitalar, o perfil é dinâmico (muitas entradas e saídas). Nesse cenário, heap tende a ser a decisão mais previsível e equilibrada.

Pro tip: Escolha estrutura pelo perfil de operações, não por preferência pessoal.