Introdução

Na parte 1 cobrimos Listas, na parte 2 cobrimos Árvores e na parte 3 cobrimos Hash Tables. Agora vamos para outra estrutura que aparece o tempo todo em agendamento, pathfinding e processamento de streams: Heaps, e o tipo abstrato construído em cima deles: Priority Queues.

Muita gente usa Priority Queue sem perceber que ela quase sempre é implementada com heap. Se você precisa repetidamente pegar o elemento de maior prioridade ou menor prioridade com eficiência, essa é uma das melhores ferramentas.

Como nos artigos anteriores, vamos manter a mesma interface base Container:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

O que é um Heap?

Heap é uma complete binary tree que satisfaz uma heap property.

Existem dois tipos comuns:

• Min-Heap: o pai é sempre menor ou igual aos filhos.
• Max-Heap: o pai é sempre maior ou igual aos filhos.

O detalhe importante: heap não é globalmente ordenado como uma BST balanceada. Ele só garante ordem entre pai e filhos. A raiz é sempre o menor (min-heap) ou o maior (max-heap).

Regra de complete binary tree

Heaps dependem de uma regra estrutural:

• todos os níveis são totalmente preenchidos, exceto possivelmente o último
• o último nível é preenchido da esquerda para a direita

Essa regra é o que torna a representação por array eficiente.

graph TD
  N10["10"] --> N20["20"]
  N10 --> N15["15"]
  N20 --> N30["30"]
  N20 --> N40["40"]
  N15 --> N50["50"]

Representação em array

Ao invés de guardar ponteiros como uma árvore comum, heap normalmente é armazenado em slice/array.

Para índice i:

• filho esquerdo: 2*i + 1
• filho direito: 2*i + 2
• pai: (i - 1) / 2

flowchart LR
  A["Array: [10, 20, 15, 30, 40, 50]"] --> B["i=0 => value=10"]
  B --> C["left=1 => 20"]
  B --> D["right=2 => 15"]

Esse layout entrega:

• sem alocação de nós por inserção
• ótima localidade de cache
• uso de memória compacto

Operações centrais do heap

Insert (Push)

1. Adiciona valor no final.
2. Restaura heap property com sift-up.

Sift-up compara o novo nó com o pai e troca enquanto a propriedade estiver violada.

flowchart TD
  A["Append no final"] --> B["Compara com o pai"]
  B --> C{"viola heap property?"}
  C -->|Sim| D["Troca com pai"]
  D --> B
  C -->|Não| E["Fim"]

Extract root (Pop)

1. Salva o valor da raiz.
2. Move o último elemento para a raiz.
3. Remove a última posição.
4. Restaura heap property com sift-down.

Sift-down compara a raiz com os filhos e troca com o melhor filho até ficar válido.

flowchart TD
  A["Remove raiz"] --> B["Move último para a raiz"]
  B --> C["sift-down da raiz"]
  C --> D{"filho é melhor que pai?"}
  D -->|Sim| E["Troca e continua"]
  E --> D
  D -->|Não| F["Fim"]

Complexidade

Para um heap binário com n elementos:

• Peek: O(1)
• Push: O(log n)
• Pop: O(log n)
• Build heap a partir de array (heapify): O(n)

O O(log n) vem da altura da árvore, e complete binary trees têm altura log n.

Implementação prática em Go (MinHeap)

Esta implementação usa int para ficar direta e segue Container.

type MinHeap struct {
  data []int
}

func NewMinHeap(values ...int) *MinHeap {
  h := &MinHeap{data: append([]int{}, values...)}
  h.buildHeap()
  return h
}

func (h *MinHeap) Empty() bool {
  return len(h.data) == 0
}

func (h *MinHeap) Size() int {
  return len(h.data)
}

func (h *MinHeap) Clear() {
  h.data = nil
}

func (h *MinHeap) Values() []interface{} {
  values := make([]interface{}, len(h.data))
  for i, v := range h.data {
    values[i] = v
  }
  return values
}

func (h *MinHeap) String() string {
  return fmt.Sprintf("%v", h.data)
}

func (h *MinHeap) Peek() (int, bool) {
  if len(h.data) == 0 {
    return 0, false
  }
  return h.data[0], true
}

func (h *MinHeap) Push(value int) {
  h.data = append(h.data, value)
  h.siftUp(len(h.data) - 1)
}

func (h *MinHeap) Pop() (int, bool) {
  if len(h.data) == 0 {
    return 0, false
  }

  root := h.data[0]
  last := len(h.data) - 1
  h.data[0] = h.data[last]
  h.data = h.data[:last]

  if len(h.data) > 0 {
    h.siftDown(0)
  }

  return root, true
}

func (h *MinHeap) buildHeap() {
  for i := len(h.data)/2 - 1; i >= 0; i-- {
    h.siftDown(i)
  }
}

func (h *MinHeap) siftUp(i int) {
  for i > 0 {
    parent := (i - 1) / 2
    if h.data[parent] <= h.data[i] {
      break
    }
    h.data[parent], h.data[i] = h.data[i], h.data[parent]
    i = parent
  }
}

func (h *MinHeap) siftDown(i int) {
  n := len(h.data)

  for {
    left := 2*i + 1
    right := 2*i + 2
    smallest := i

    if left < n && h.data[left] < h.data[smallest] {
      smallest = left
    }
    if right < n && h.data[right] < h.data[smallest] {
      smallest = right
    }
    if smallest == i {
      break
    }

    h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
    i = smallest
  }
}

Import usado:

import "fmt"

De Heap para Priority Queue

Priority Queue é uma estrutura abstrata onde cada elemento tem prioridade e a extração sempre retorna o item de maior prioridade (ou menor, dependendo da convenção).

Heap é a implementação mais comum porque entrega O(log n) para inserção/remoção e O(1) para acesso ao próximo item.

flowchart LR
  A["Priority Queue API"] --> B["Enqueue(value, priority)"]
  A --> C["Dequeue()"]
  B --> D["Inserção no heap"]
  C --> E["Extração da raiz do heap"]

Implementação prática em Go (PriorityQueue)

Abaixo implementamos uma min-priority queue (menor número de prioridade significa maior prioridade).

type PQItem[T any] struct {
  Value    T
  Priority int
}

type PriorityQueue[T any] struct {
  heap []PQItem[T]
}

func NewPriorityQueue[T any]() *PriorityQueue[T] {
  return &PriorityQueue[T]{heap: make([]PQItem[T], 0)}
}

func (pq *PriorityQueue[T]) Empty() bool {
  return len(pq.heap) == 0
}

func (pq *PriorityQueue[T]) Size() int {
  return len(pq.heap)
}

func (pq *PriorityQueue[T]) Clear() {
  pq.heap = nil
}

func (pq *PriorityQueue[T]) Values() []interface{} {
  out := make([]interface{}, len(pq.heap))
  for i := range pq.heap {
    out[i] = pq.heap[i]
  }
  return out
}

func (pq *PriorityQueue[T]) String() string {
  return fmt.Sprintf("%v", pq.heap)
}

func (pq *PriorityQueue[T]) Enqueue(value T, priority int) {
  pq.heap = append(pq.heap, PQItem[T]{Value: value, Priority: priority})
  pq.siftUp(len(pq.heap) - 1)
}

func (pq *PriorityQueue[T]) Peek() (PQItem[T], bool) {
  if len(pq.heap) == 0 {
    return PQItem[T]{}, false
  }
  return pq.heap[0], true
}

func (pq *PriorityQueue[T]) Dequeue() (PQItem[T], bool) {
  if len(pq.heap) == 0 {
    return PQItem[T]{}, false
  }

  top := pq.heap[0]
  last := len(pq.heap) - 1
  pq.heap[0] = pq.heap[last]
  pq.heap = pq.heap[:last]

  if len(pq.heap) > 0 {
    pq.siftDown(0)
  }

  return top, true
}

func (pq *PriorityQueue[T]) siftUp(i int) {
  for i > 0 {
    parent := (i - 1) / 2
    if pq.heap[parent].Priority <= pq.heap[i].Priority {
      break
    }
    pq.heap[parent], pq.heap[i] = pq.heap[i], pq.heap[parent]
    i = parent
  }
}

func (pq *PriorityQueue[T]) siftDown(i int) {
  n := len(pq.heap)

  for {
    left := 2*i + 1
    right := 2*i + 2
    best := i

    if left < n && pq.heap[left].Priority < pq.heap[best].Priority {
      best = left
    }
    if right < n && pq.heap[right].Priority < pq.heap[best].Priority {
      best = right
    }
    if best == i {
      break
    }

    pq.heap[i], pq.heap[best] = pq.heap[best], pq.heap[i]
    i = best
  }
}

Casos de uso reais

• Agendamento de tarefas: próxima tarefa por deadline/prioridade.
• Algoritmos de grafo: Dijkstra e A* usam priority queues.
• Simulação de eventos: processar evento mais cedo primeiro.
• Rate limiting e retries: próximo retry por timestamp.
• Top-k em streams: manter os melhores candidatos com eficiência.

Heap vs Hash Table vs Balanced Tree

• Use Heap/Priority Queue quando a operação principal for extrair repetidamente o próximo melhor elemento.
• Use Hash Table quando a operação principal for lookup exato por chave.
• Use Balanced Tree quando precisar de iteração ordenada e operações de intervalo.

Cada estrutura otimiza uma pergunta diferente. A escolha correta depende do padrão de acesso.

Conclusão

Heaps e Priority Queues são essenciais quando ordem por prioridade importa mais do que lookup aleatório. O ponto forte é performance previsível com operações simples: push, peek e pop em tempo logarítmico.

Neste artigo cobrimos estrutura, propriedades, mecânica de sift-up/sift-down e implementações práticas em Go, mantendo o mesmo padrão de Container usado ao longo da série.

Na próxima parte podemos entrar em Graphs e algoritmos de travessia/caminho, que se conectam naturalmente com priority queues.