Heap e Priority Queue em Go: do conceito ao mundo real

Visão geral

Tenho estudado estruturas de dados em Go mais a fundo, e uma das que mais me chamou atenção foi a heap — não pelo conceito em si, mas por perceber o quanto ela está presente em coisas que uso todo dia sem nem notar. GPS, agendadores de tarefas, sistemas de triagem, algoritmos de grafos... tudo isso usa heap por baixo dos panos.

Neste post quero documentar o que aprendi: o que é uma heap, como implementá-la em Go usando o pacote container/heap, e onde ela aparece de verdade.

O que é uma Heap?

Uma heap é uma árvore binária completa com uma propriedade especial: cada nó pai é sempre menor ou igual aos seus filhos (min-heap) — ou maior ou igual (max-heap).

A propriedade mais importante: o elemento de maior prioridade está sempre na raiz, acessível em O(1).

Complexidade das operações

Representação como slice

A heap não é armazenada como uma árvore de ponteiros — ela usa um slice, com a seguinte convenção de índices:

• Pai do nó i: (i - 1) / 2
• Filho esquerdo do nó i: 2*i + 1
• Filho direito do nó i: 2*i + 2

Isso torna a heap extremamente eficiente em memória e cache-friendly.

Heap em Go: o pacote container/heap

Go não tem uma priority queue nativa, mas o pacote container/heap da stdlib fornece todas as operações de heap. Você só precisa implementar a interface heap.Interface:

type Interface interface {
    sort.Interface          // Len(), Less(i, j int) bool, Swap(i, j)
    Push(x any)             // adiciona elemento
    Pop() any               // remove e retorna o último elemento
}

Exemplo 1 — Min-Heap de inteiros

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x any) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func main() {
    h := &MinHeap{5, 2, 8, 1, 9}
    heap.Init(h)

    heap.Push(h, 3)

    fmt.Println("Menor elemento:", (*h)[0]) // 1

    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
    // Output: 1 2 3 5 8 9
}

Exemplo 2 — Priority Queue com structs (exemplo oficial da stdlib)

Este é o padrão recomendado pela documentação oficial do Go:

package main

import (
    "container/heap"
    "fmt"
)

type Item struct {
    value    string
    priority int
    index    int // posição no heap, necessária para heap.Fix
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

// max-heap: maior prioridade sai primeiro
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(x any) {
    n := len(*pq)
    item := x.(*Item)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() any {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // evita memory leak
    item.index = -1 // segurança
    *pq = old[:n-1]
    return item
}

// atualiza prioridade de um item já inserido
func (pq *PriorityQueue) update(item *Item, value string, priority int) {
    item.value = value
    item.priority = priority
    heap.Fix(pq, item.index) // reposiciona o item sem reconstruir a heap
}

func main() {
    pq := &PriorityQueue{}
    heap.Init(pq)

    heap.Push(pq, &Item{value: "tarefa normal", priority: 2})
    heap.Push(pq, &Item{value: "tarefa urgente", priority: 10})
    heap.Push(pq, &Item{value: "tarefa baixa", priority: 1})

    for pq.Len() > 0 {
        item := heap.Pop(pq).(*Item)
        fmt.Printf("[prioridade %d] %s\n", item.priority, item.value)
    }
    // Output:
    // [prioridade 10] tarefa urgente
    // [prioridade 2] tarefa normal
    // [prioridade 1] tarefa baixa
}

heap.Fix — atualizando prioridades dinamicamente

Um ponto pouco discutido: e se a prioridade de um item mudar depois de ele já estar na heap?

O Go resolve isso com heap.Fix(h, i) — ele reposiciona o elemento no índice i sem precisar reconstruir a heap inteira. Complexidade: O(log n).

item := heap.Pop(pq).(*Item) // remove
// ... não precisa fazer isso se usar Fix

pq.update(item, item.value, 99) // atualiza prioridade e reposiciona

Isso é fundamental para algoritmos como Dijkstra, onde as distâncias dos nós são atualizadas conforme o grafo é explorado.

Onde a heap aparece no mundo real?

1. Algoritmo de Dijkstra (menor caminho em grafos)

Todo GPS usa isso. A priority queue garante que o nó com menor distância acumulada seja sempre processado primeiro.

// simplificado
type Node struct {
    id   int
    dist int
}
type NodeHeap []Node
// Less: return h[i].dist < h[j].dist — min-heap por distância

2. Agendadores de tarefas e event loops

Sistemas como o scheduler do Go runtime, timers de sistemas operacionais e event loops de servidores usam heaps para saber qual é o próximo evento a disparar — sempre o de menor timestamp.

3. Top-K elementos

"Quais são os 10 produtos mais acessados?" — em vez de ordenar tudo (O(n log n)), mantém uma min-heap de tamanho K: se o novo elemento é maior que o menor da heap, substitui. Resultado em O(n log K).

func topK(nums []int, k int) []int {
    h := &MinHeap{}
    heap.Init(h)
    for _, n := range nums {
        heap.Push(h, n)
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    return []int(*h)
}

4. Merge de N listas ordenadas

Para mesclar N listas já ordenadas (ex: resultados de múltiplas buscas), a heap mantém o menor elemento atual de cada lista, processando sempre o mínimo global em O(total * log N).

5. Sistemas de triagem e filas hospitalares

Um paciente em estado crítico não entra no final da fila — ele tem prioridade. A priority queue é exatamente esse modelo: independe da ordem de chegada, processa o mais urgente primeiro.

Cuidado: container/heap não é thread-safe

Se você usar a heap em cenários concorrentes (múltiplas goroutines fazendo Push/Pop ao mesmo tempo), é necessário protegê-la com sync.Mutex:

type SafePQ struct {
    mu sync.Mutex
    pq PriorityQueue
}

func (s *SafePQ) Push(item *Item) {
    s.mu.Lock()
    defer s.mu.Unlock()
    heap.Push(&s.pq, item)
}

A razão é a mesma do map nativo: a decisão de sincronização é deixada para o usuário, que sabe melhor o contexto da aplicação.

Conclusão

A heap foi uma das estruturas que mais me fez pensar: "como eu nunca parei pra entender isso direito antes?". Ela é simples conceitualmente, eficiente na prática, e está por baixo de muita coisa que usamos no dia a dia como engenheiros.

Se você quiser se aprofundar, a documentação oficial do container/heap tem exemplos completos e é bem didática.