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. 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
- Construir max-heap: transforme o array em um max-heap (pai sempre maior que filhos)
- Extrair máximo: troque a raiz (maior) com o último elemento
- Reduzir heap: diminua o tamanho do heap em 1 e restaure a propriedade de heap
- 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
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 | 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