--- title: "Heap Sort em Zig — Implementação e Explicação" url: "https://ziglang.com.br/algoritmos/heap-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o/" markdown_url: "https://ziglang.com.br/algoritmos/heap-sort-em-zig-implementa%C3%A7%C3%A3o-e-explica%C3%A7%C3%A3o.MD" description: "Aprenda o algoritmo Heap Sort implementado em Zig. Explicação completa com código funcional, uso de heap binário e análise de complexidade O(n log n)." date: "2026-02-21" author: "Zig Brasil" --- # Heap Sort em Zig — Implementação e Explicação Aprenda o algoritmo Heap Sort implementado em Zig. Explicação completa com código funcional, uso de heap binário e análise de complexidade O(n log n). # Heap Sort em Zig — Implementação e Explicação O **Heap Sort** é um algoritmo de ordenação baseado na estrutura de dados [heap binário](/estruturas-dados/heap-binario/). Ele utiliza um max-heap para extrair repetidamente o maior elemento e posicioná-lo no final do array, construindo a sequência ordenada de trás para frente. ## Como Funciona 1. **Construir max-heap**: transforme o array em um max-heap (pai sempre maior que filhos) 2. **Extrair máximo**: troque a raiz (maior) com o último elemento 3. **Reduzir heap**: diminua o tamanho do heap em 1 e restaure a propriedade de heap 4. **Repetir**: continue até o heap ter tamanho 1 ### Representação do Heap como Array ``` Árvore: Array: [90, 80, 70, 50, 60, 10, 40] 90 / \ Pai de i: (i-1)/2 80 70 Filho esq: 2*i + 1 / \ / \ Filho dir: 2*i + 2 50 60 10 40 ``` ### Visualização do Processo ``` Array: [4, 10, 3, 5, 1] 1. Construir max-heap: [10, 5, 3, 4, 1] → heap válido 2. Troca raiz (10) com último: [1, 5, 3, 4, | 10] → heapify [5, 4, 3, 1, | 10] 3. Troca raiz (5) com último: [1, 4, 3, | 5, 10] → heapify [4, 1, 3, | 5, 10] 4. Troca raiz (4) com último: [3, 1, | 4, 5, 10] → heapify [3, 1, | 4, 5, 10] 5. Troca raiz (3) com último: [1, | 3, 4, 5, 10] Resultado: [1, 3, 4, 5, 10] ✓ ``` ## Implementação em Zig ```zig const std = @import("std"); /// Heap Sort genérico — ordena in-place em O(n log n). pub fn heapSort(comptime T: type, items: []T) void { const len = items.len; if (len <= 1) return; // Fase 1: construir max-heap (bottom-up) // Começa do último nó não-folha var i: usize = len / 2; while (i > 0) { i -= 1; heapify(T, items, len, i); } // Fase 2: extrair elementos do heap um a um var tamanho: usize = len; while (tamanho > 1) { tamanho -= 1; // Troca a raiz (maior) com o último elemento do heap const temp = items[0]; items[0] = items[tamanho]; items[tamanho] = temp; // Restaura a propriedade de max-heap heapify(T, items, tamanho, 0); } } /// Restaura a propriedade de max-heap a partir do índice i. /// "Afunda" o elemento na posição i até sua posição correta. fn heapify(comptime T: type, items: []T, heap_size: usize, i: usize) void { var maior: usize = i; const esq = 2 * i + 1; // filho esquerdo const dir = 2 * i + 2; // filho direito // Verifica se o filho esquerdo é maior que a raiz if (esq < heap_size and items[esq] > items[maior]) { maior = esq; } // Verifica se o filho direito é maior que o maior até agora if (dir < heap_size and items[dir] > items[maior]) { maior = dir; } // Se o maior não é a raiz, troca e continua if (maior != i) { const temp = items[i]; items[i] = items[maior]; items[maior] = temp; // Recursivamente restaura o sub-heap afetado heapify(T, items, heap_size, maior); } } /// Versão iterativa do heapify (sem recursão, evita stack overflow). fn heapifyIterativo(comptime T: type, items: []T, heap_size: usize, start: usize) void { var i = start; while (true) { var maior = i; const esq = 2 * i + 1; const dir = 2 * i + 2; if (esq < heap_size and items[esq] > items[maior]) maior = esq; if (dir < heap_size and items[dir] > items[maior]) maior = dir; if (maior == i) break; const temp = items[i]; items[i] = items[maior]; items[maior] = temp; i = maior; } } /// Heap Sort com comparador personalizado. pub fn heapSortBy( comptime T: type, items: []T, comptime lessThan: fn (T, T) bool, ) void { const len = items.len; if (len <= 1) return; var i: usize = len / 2; while (i > 0) { i -= 1; heapifyBy(T, items, len, i, lessThan); } var tamanho: usize = len; while (tamanho > 1) { tamanho -= 1; const temp = items[0]; items[0] = items[tamanho]; items[tamanho] = temp; heapifyBy(T, items, tamanho, 0, lessThan); } } fn heapifyBy( comptime T: type, items: []T, heap_size: usize, start: usize, comptime lessThan: fn (T, T) bool, ) void { var i = start; while (true) { var maior = i; const esq = 2 * i + 1; const dir = 2 * i + 2; if (esq < heap_size and lessThan(items[maior], items[esq])) maior = esq; if (dir < heap_size and lessThan(items[maior], items[dir])) maior = dir; if (maior == i) break; const temp = items[i]; items[i] = items[maior]; items[maior] = temp; i = maior; } } pub fn main() !void { const stdout = std.io.getStdOut().writer(); var numeros = [_]i32{ 12, 11, 13, 5, 6, 7 }; try stdout.print("Original: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); heapSort(i32, &numeros); try stdout.print("Ordenado: ", .{}); for (numeros) |n| try stdout.print("{d} ", .{n}); try stdout.print("\n", .{}); } ``` ## Análise de Complexidade | Caso | Tempo | Espaço | |------|-------|--------| | **Melhor caso** | O(n log n) | O(1) | | **Caso médio** | O(n log n) | O(1) | | **Pior caso** | O(n log n) | O(1) | ### Detalhamento - **Construção do heap**: O(n) — heapify bottom-up é linear - **Extração de n elementos**: cada extração é O(log n), total O(n log n) - **Espaço**: O(1) in-place (ou O(log n) se heapify for recursivo) ## Características - **Estável**: Não — trocas com a raiz alteram ordem de iguais - **In-place**: Sim — usa O(1) de memória adicional - **Desempenho garantido**: O(n log n) em todos os casos - **Cache-unfriendly**: acessos ao heap não são sequenciais na memória ## Heap Sort vs Outros O(n log n) | Aspecto | Heap Sort | [Quick Sort](/algoritmos/quick-sort/) | [Merge Sort](/algoritmos/merge-sort/) | |---------|-----------|-----------|-----------| | Pior caso | O(n log n) | O(n²) | O(n log n) | | Espaço | O(1) | O(log n) | O(n) | | Estável | Não | Não | Sim | | Cache | Ruim | Excelente | Bom | | Prática | Mais lento | Mais rápido | Previsível | ## Recursos Relacionados - [Heap Binário](/estruturas-dados/heap-binario/) — Estrutura de dados usada pelo Heap Sort - [Quick Sort em Zig](/algoritmos/quick-sort/) — Alternativa geralmente mais rápida - [Merge Sort em Zig](/algoritmos/merge-sort/) — Alternativa estável - [Selection Sort em Zig](/algoritmos/selection-sort/) — Versão ingênua da ideia de seleção - [Fila de Prioridade](/estruturas-dados/heap-binario/) — Aplicação principal do heap