Heap (heap binário)
Última atualização
Um heap binário é uma árvore binária completa que mantém o menor (min-heap) ou o maior (max-heap) valor na raiz. Esta visualização é um min-heap: cada pai é menor ou igual aos seus filhos. Para adicionar um valor você o insere na próxima posição livre e depois o "faz subir", trocando-o com o pai enquanto for menor, até que a propriedade de heap seja satisfeita novamente. Pressione reproduzir acima para ver cada novo valor subir até o seu lugar.
Como um heap é uma árvore completa, ele é armazenado de forma compacta em um array: os filhos do nó i ficam em 2i+1 e 2i+2. Inserir e remover o mínimo são O(log n) (um caminho da raiz até uma folha), enquanto consultar o mínimo é O(1) - exatamente o que uma fila de prioridade precisa.
Complexidade de tempo e espaço
| Operação | Complexidade | Notas |
|---|---|---|
| Consultar mín/máx | O(1) | É sempre a raiz |
| Inserir (push) | O(log n) | Subir por um caminho |
| Remover mín/máx | O(log n) | Descer por um caminho |
| Construir o heap | O(n) | Heapify de uma vez |
| Espaço | O(n) | Baseado em array, sem ponteiros |
Passo a passo (push)
| Passo | O que acontece |
|---|---|
| 1 | Adicione o novo valor ao final (a próxima folha livre). |
| 2 | Compare-o com o seu pai. |
| 3 | Se for menor (min-heap), troque-o para cima. |
| 4 | Repita até que não seja mais menor que o pai ou alcance a raiz. |
Exemplo resolvido
Construindo um min-heap ao inserir [5, 3, 8, 1, 4] um valor por vez:
| Push | Array após subir | Ação |
|---|---|---|
5 | [5] | O primeiro valor torna-se a raiz. |
3 | [3, 5] | 3 < pai 5, então sobe até a raiz. |
8 | [3, 5, 8] | 8 > pai 5, então permanece como folha. |
1 | [1, 3, 8, 5] | 1 < pai 5, troca; depois 1 < pai 3, sobe até a raiz. |
4 | [1, 3, 8, 5, 4] | 4 > pai 3, então permanece; o mínimo 1 continua na raiz. |
Quando usar um heap
| Use quando | Evite quando |
|---|---|
| Você precisa repetidamente do menor ou maior item de um conjunto que muda. | Você precisa buscar valores arbitrários, não apenas o extremo - use um BST ou um conjunto hash. |
| Você está implementando uma fila de prioridade para Dijkstra, A* ou um agendador. | Você precisa manter os dados totalmente ordenados o tempo todo. |
Você quer inserção e remoção do mínimo em O(log n) com um layout de array compacto. | Você precisa de busca ou remoção rápida de um elemento específico (não a raiz). |
| Você precisa mesclar um fluxo de itens e retirá-los por prioridade. | O conjunto de dados é minúsculo e uma varredura linear é mais simples e rápida o bastante. |
Código de Heap (Priority Queue)
Uma implementação limpa e executável de Heap (Priority Queue) em Python, JavaScript, Java, C++, C. Escolha uma linguagem, copie o código ou abra-o já carregado no Playground da Coddy.
Código de Heap (Priority Queue) em Python
Python
1class MinHeap:2 def __init__(self):3 self.data = []4
5 def push(self, value):6 # Append at the end, then bubble up to restore order7 self.data.append(value)8 i = len(self.data) - 19 while i > 0:10 parent = (i - 1) // 211 if self.data[parent] <= self.data[i]:12 break13 self.data[i], self.data[parent] = self.data[parent], self.data[i]14 i = parent15
16 def pop(self):17 # Move the last leaf to the root, then sift it down18 top = self.data[0]19 last = self.data.pop()20 if self.data:21 self.data[0] = last22 self._sift_down(0)23 return top24
25 def _sift_down(self, i):26 n = len(self.data)27 while True:28 smallest = i29 left, right = 2 * i + 1, 2 * i + 230 if left < n and self.data[left] < self.data[smallest]:31 smallest = left32 if right < n and self.data[right] < self.data[smallest]:33 smallest = right34 if smallest == i:35 return36 self.data[i], self.data[smallest] = self.data[smallest], self.data[i]37 i = smallest38
39
40heap = MinHeap()41for value in [5, 3, 8, 1, 9, 2]:42 heap.push(value)43
44print("Heap array: ", heap.data)45print("Popped in order:", [heap.pop() for _ in range(6)])Código de Heap (Priority Queue) em JavaScript
JavaScript
1class MinHeap {2 constructor() {3 this.items = [];4 }5
6 push(value) {7 this.items.push(value);8 // Bubble the new value up while it is smaller than its parent9 let i = this.items.length - 1;10 while (i > 0) {11 const parent = Math.floor((i - 1) / 2);12 if (this.items[parent] <= this.items[i]) break;13 [this.items[parent], this.items[i]] = [this.items[i], this.items[parent]];14 i = parent;15 }16 }17
18 pop() {19 const top = this.items[0];20 const last = this.items.pop();21 if (this.items.length > 0) {22 this.items[0] = last;23 this.sinkDown(0);24 }25 return top;26 }27
28 sinkDown(i) {29 const n = this.items.length;30 while (true) {31 let smallest = i;32 const left = 2 * i + 1;33 const right = 2 * i + 2;34 if (left < n && this.items[left] < this.items[smallest]) smallest = left;35 if (right < n && this.items[right] < this.items[smallest]) smallest = right;36 if (smallest === i) return;37 [this.items[i], this.items[smallest]] = [this.items[smallest], this.items[i]];38 i = smallest;39 }40 }41}42
43const heap = new MinHeap();44for (const value of [5, 2, 9, 1, 7, 3]) heap.push(value);45const sorted = [];46while (heap.items.length > 0) sorted.push(heap.pop());47console.log("Popped in order:", sorted.join(" "));Código de Heap (Priority Queue) em Java
Java
1public class Main {2 static int[] heap = new int[32];3 static int size = 0;4
5 static void push(int value) {6 heap[size] = value;7 int i = size++;8 // Sift up while smaller than the parent9 while (i > 0 && heap[(i - 1) / 2] > heap[i]) {10 swap(i, (i - 1) / 2);11 i = (i - 1) / 2;12 }13 }14
15 static int pop() {16 int min = heap[0];17 heap[0] = heap[--size];18 int i = 0;19 // Sift down: swap with the smaller child until in place20 while (true) {21 int smallest = i, l = 2 * i + 1, r = 2 * i + 2;22 if (l < size && heap[l] < heap[smallest]) smallest = l;23 if (r < size && heap[r] < heap[smallest]) smallest = r;24 if (smallest == i) break;25 swap(i, smallest);26 i = smallest;27 }28 return min;29 }30
31 static void swap(int a, int b) {32 int tmp = heap[a];33 heap[a] = heap[b];34 heap[b] = tmp;35 }36
37 public static void main(String[] args) {38 int[] values = {9, 4, 7, 1, 8, 2};39 for (int v : values) push(v);40 System.out.print("Popped in order:");41 while (size > 0) System.out.print(" " + pop());42 System.out.println();43 }44}Código de Heap (Priority Queue) em C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5struct MinHeap {6 std::vector<int> data;7
8 void push(int value) {9 data.push_back(value);10 // Sift up until the parent is no larger11 size_t i = data.size() - 1;12 while (i > 0) {13 size_t parent = (i - 1) / 2;14 if (data[parent] <= data[i]) break;15 std::swap(data[parent], data[i]);16 i = parent;17 }18 }19
20 int pop() {21 int top = data[0];22 data[0] = data.back();23 data.pop_back();24 // Sift down: swap with the smaller child25 size_t i = 0;26 while (true) {27 size_t l = 2 * i + 1, r = 2 * i + 2, smallest = i;28 if (l < data.size() && data[l] < data[smallest]) smallest = l;29 if (r < data.size() && data[r] < data[smallest]) smallest = r;30 if (smallest == i) break;31 std::swap(data[i], data[smallest]);32 i = smallest;33 }34 return top;35 }36
37 int peek() const { return data[0]; }38 bool empty() const { return data.empty(); }39};40
41int main() {42 MinHeap heap;43 for (int value : {5, 3, 8, 1, 9, 2}) heap.push(value);44 std::cout << "Min: " << heap.peek() << "\n";45 std::cout << "Popped in order: ";46 while (!heap.empty()) std::cout << heap.pop() << " ";47 std::cout << "\n";48 return 0;49}Código de Heap (Priority Queue) em C
C
1#include <stdio.h>2
3#define CAP 644
5int heap[CAP];6int heapSize = 0;7
8void push(int value) {9 // Sift up until the parent is no larger10 int i = heapSize++;11 heap[i] = value;12 while (i > 0) {13 int parent = (i - 1) / 2;14 if (heap[parent] <= heap[i]) break;15 int tmp = heap[parent];16 heap[parent] = heap[i];17 heap[i] = tmp;18 i = parent;19 }20}21
22int pop(void) {23 int top = heap[0];24 heap[0] = heap[--heapSize];25 // Sift down: swap with the smaller child26 int i = 0;27 while (1) {28 int l = 2 * i + 1, r = 2 * i + 2, smallest = i;29 if (l < heapSize && heap[l] < heap[smallest]) smallest = l;30 if (r < heapSize && heap[r] < heap[smallest]) smallest = r;31 if (smallest == i) break;32 int tmp = heap[i];33 heap[i] = heap[smallest];34 heap[smallest] = tmp;35 i = smallest;36 }37 return top;38}39
40int main(void) {41 int values[] = {5, 3, 8, 1, 9, 2};42 for (int i = 0; i < 6; i++) push(values[i]);43 printf("Min: %d\n", heap[0]);44 printf("Popped in order: ");45 while (heapSize > 0) printf("%d ", pop());46 printf("\n");47 return 0;48}Perguntas frequentes sobre heaps
Para que serve um heap?
Heaps implementam filas de prioridade, que alimentam o algoritmo de caminho mais curto de Dijkstra, agendadores de tarefas e simulações de eventos. Também são o motor por trás do heapsort. Sempre que você precisar repetidamente do menor ou maior item de um conjunto que muda, um heap é a ferramenta.
Qual é a diferença entre um heap e uma árvore binária de busca?
Ambos são árvores binárias, mas uma BST mantém uma ordem completa da esquerda para a direita (permitindo busca ordenada), enquanto um heap só garante a relação pai-filho (mínimo ou máximo na raiz). Um heap dá acesso O(1) ao valor extremo; uma BST dá busca O(log n) para qualquer valor.
Por que um heap é armazenado em um array?
Como um heap é sempre uma árvore binária completa, seus nós mapeiam perfeitamente para índices de array: os filhos do índice
i ficam em 2i+1 e 2i+2, e o pai em (i-1)/2. Isso evita armazenar ponteiros para os filhos e oferece excelente desempenho de cache.Um heap é o mesmo que um array ordenado?
Não. Um heap só garante que cada pai seja menor (min-heap) ou maior (max-heap) que seus filhos, então irmãos e primos não têm ordem particular. Um array ordenado é totalmente ordenado, mas custa
O(n) para inserir, enquanto um heap insere em O(log n) e ainda dá acesso instantâneo ao valor extremo.Quando devo usar um heap em vez de simplesmente ordenar um array?
Recorra a um heap quando os dados mudam constantemente e você só precisa do mínimo ou máximo atual - inserir e retirar custam
O(log n) cada, contra reordenar o array inteiro. Se você tem um conjunto de dados estático e quer todos os elementos em ordem, uma única ordenação O(n log n) é mais simples e muitas vezes mais rápida.Construir um heap com n itens custa O(n log n)?
Não se você construí-lo de uma só vez. Inserir
n itens um a um é O(n log n), mas o heapify de baixo para cima, que desce do último pai até a raiz, roda em O(n) no total, porque a maioria dos nós está perto do fundo e desce apenas uma distância curta.Recursos relacionados
Mais visualizações
