Heap Sort
O heap sort é o que acontece quando você pega o binary heap e resolve levar a ideia até o fim: se remover o maior custa O(log n), remover n vezes ordena o array inteiro em O(n log n). O detalhe que faz dele um algoritmo de verdade, e não só um heap com laço em volta, é que ele consegue fazer isso dentro do próprio array, sem alocar um único byte a mais.
Ordenar é remover o topo n vezes
Existe um algoritmo de ordenação que quase todo mundo inventa sozinho antes de estudar o assunto: percorra o array, ache o maior, coloque no fim; percorra de novo, ache o segundo maior, coloque na penúltima posição; repita. É o selection sort, e ele está correto.
O problema dele não é a ideia, é a busca. Achar o maior por varredura custa uma passada inteira, e são n passadas: n + (n-1) + (n-2) + ..., ou seja, n(n-1)/2 comparações, o que é O(n²). Com 1 milhão de elementos isso dá cerca de 5 × 10¹¹ comparações.
Agora troque a varredura por um max-heap. A ideia continua idêntica, mas achar o maior passa a custar O(1) e removê-lo O(log n). O total cai para cerca de 2 × 10⁷, algo em torno de vinte e cinco mil vezes menos trabalho, sem mudar uma linha da estratégia.
Heap sort é selection sort com a estrutura de dados certa. Todo o resto do artigo é sobre como fazer isso sem gastar memória extra.
Fase 1: virar o array num max-heap
O array chega cru, sem garantia nenhuma. A primeira coisa é transformá-lo num max-heap, e isso é feito exatamente como no tópico anterior: descendo a partir do último nó que tem filho, de trás para a frente.
def build_heap(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1):
desce(a, i, n)Começar em n // 2 - 1 descarta metade do array de saída, porque da metade para a frente só existe folha. Essa fase custa O(n), não O(n log n), pela soma que fecha em n: a maioria esmagadora dos nós desce pouco ou nada, e só a raiz desce a altura inteira.
Terminada a fase 1 o array continua parecendo embaralhado, e está tudo certo. A única coisa que ela promete é que o maior valor está na posição 0, e é só disso que a próxima fase precisa.
Fase 2: a fronteira que anda para trás
Aqui está a parte que confunde, e é a única novidade real do heap sort.
O maior valor está em a[0] e o lugar definitivo dele é o fim do array. Então: troque a[0] com a[n-1]. Pronto, a última posição está resolvida para sempre. Só que agora a raiz tem um valor qualquer e o heap quebrou, então basta descer a raiz de novo.
E aqui vem o truque: ao descer, o algoritmo finge que o array tem um elemento a menos. A posição que acabou de receber o maior valor não faz mais parte do heap, e nenhuma comparação pode enxergá-la, senão o valor voltaria a subir.
def heap_sort(a):
n = len(a)
for i in range(n // 2 - 1, -1, -1): # fase 1
desce(a, i, n)
for fim in range(n - 1, 0, -1): # fase 2
a[0], a[fim] = a[fim], a[0]
desce(a, 0, fim) # 'fim' vira o novo tamanho
def desce(a, i, n): # n = até onde o heap ainda vale
while True:
maior, e, d = i, 2 * i + 1, 2 * i + 2
if e < n and a[e] > a[maior]: maior = e
if d < n and a[d] > a[maior]: maior = d
if maior == i: return
a[i], a[maior] = a[maior], a[i]
i = maiorO n do desce é o parâmetro mais importante do algoritmo. Ele é a fronteira: à esquerda dela mora um heap válido, à direita mora o resultado final já ordenado, e as duas regiões dividem o mesmo array. A cada rodada a fronteira anda uma posição para a esquerda.
Acompanhe isso acontecendo. Repare na faixa verde crescendo da direita para a esquerda e no card "heap ativo" diminuindo:
O caso comum. Acompanhe a fronteira verde crescendo da direita para a esquerda: cada rodada da fase 2 congela mais uma posição, e ela nunca mais é tocada.
Entrada: 4, 10, 3, 5, 1, 8, 7, 2, 9, 6. Vou ordenar dentro deste mesmo array, sem alocar nada, em duas fases: primeiro viro tudo num max-heap, depois arranco o maior repetidas vezes.
Rode até o fim nos presets "embaralhado", "já ordenado" e "ao contrário" e anote o total de comparações: 38, 41 e 35. Dez valores, três entradas radicalmente diferentes, e o array já ordenado é justamente o que dá MAIS trabalho. Essa insensibilidade à entrada é a promessa do heap sort: o pior caso é igual ao melhor, e nenhuma entrada consegue derrubá-lo.
←→ passo · espaço roda
Essa operação não é nova: é o pop do heap escrito de outro jeito. No pop, o último elemento vai para a raiz e o array encolhe. Aqui, o topo e o último trocam de lugar e o heap encolhe. A diferença é que o valor removido não é descartado, ele fica exatamente na posição que o array acabou de liberar. Heap sort é um pop que devolve o resultado para dentro de casa.
Por que max-heap para ordenar crescente
A escolha parece invertida na primeira leitura, e a lógica é curta: o heap sort preenche o array de trás para frente. A primeira posição a ser resolvida é a última, e a última posição de um array crescente é onde mora o maior valor. Logo, o algoritmo precisa que o maior esteja acessível, e isso é um max-heap.
Inverter tudo funciona e é útil saber: um min-heap com a mesma estrutura produz o array em ordem decrescente. Na prática você não muda o algoritmo, muda o comparador, que é o mesmo mecanismo que uma biblioteca oferece quando você pede ordem inversa.
A conta: n log n no melhor e no pior caso
A fase 1 custa O(n). A fase 2 faz n - 1 rodadas, e cada uma tem uma descida que percorre no máximo a altura da árvore, ⌊log₂ n⌋. O total é O(n) + O(n log n), e como numa soma fica só o termo dominante (a regra vale a pena revisitar em Big O), o algoritmo é O(n log n).
A parte notável não é o valor, é que ele é o mesmo nos três cenários:
| Caso | Heap sort | Quick sort |
|---|---|---|
| melhor | O(n log n) | O(n log n) |
| médio | O(n log n) | O(n log n) |
| pior | O(n log n) | O(n²) |
Não existe entrada capaz de derrubar o heap sort. Ele não tem pivô para escolher errado nem atalho para entrada quase ordenada: as duas fases fazem o mesmo trabalho sempre. Dá para medir isso no visualizador acima com os mesmos dez valores em três arranjos diferentes: 38 comparações no embaralhado, 41 no já ordenado e 35 no invertido. Repare que o array já ordenado é justamente o mais caro dos três, o oposto do que acontece com o insertion sort.
Essa insensibilidade tem dois lados. Ela é uma garantia forte, que importa quando um pior caso quadrático seria inaceitável ou quando a entrada pode ser hostil de propósito. E é também o motivo de o heap sort perder em velocidade real para o quick sort na média: como ele salta entre i, 2i + 1 e 2i + 2, os acessos ficam espalhados pela memória e o cache do processador erra muito, enquanto o quick sort percorre trechos contíguos.
In-place e instável
Duas características que decidem se o heap sort serve para o seu caso.
Todas as trocas acontecem dentro do array original. A versão iterativa usa O(1) de memória extra; a recursiva usa O(log n) por causa da pilha de chamadas. Nenhum array auxiliar é criado, e é aqui que ele ganha do merge sort.
Elementos com a mesma chave podem sair em ordem diferente da que entraram. Não é bug, é consequência direta de arrancar o último elemento e jogá-lo na raiz.
"Instável" é a característica pior explicada dos algoritmos de ordenação, porque o resultado continua correto: as chaves saem em ordem. O que muda é o desempate, e isso só aparece quando o elemento tem mais coisa além da chave.
A entrada está em ordem alfabética. Ordenando por idade, o esperado é que dentro de cada idade os nomes continuem alfabéticos, e é isso que o sort estável entrega.
As duas saídas estão corretas pela chave: a sequência de chaves é idêntica nas duas. O que mudou foi o desempate. Fran entrou na posição 5 e Davi na posição 3, os dois com chave 2. O sort estável manteve essa ordem; o heap sort devolveu Fran na frente. Ninguém errou uma comparação: é que o heap arranca o último elemento do array e joga na raiz, e esse salto não tem como respeitar de onde o registro veio.
Onde isso morde de verdade: ordenações encadeadas. "Ordene por nome, depois por idade" só produz o resultado esperado se o segundo sort for estável. Com um instável você precisa comparar as duas chaves de uma vez, na mesma função de comparação, em vez de ordenar duas vezes.
O cenário do primeiro preset é o que morde na prática. Uma lista em ordem alfabética (Ana, Bia, Caio, Davi, Enzo, Fran) sendo reordenada por idade: com um sort estável, os nomes continuam alfabéticos dentro de cada idade; com o heap sort, os três pares empatados saem invertidos de uma vez.
Instável não quer dizer "sempre inverte", quer dizer "não garante nada". O segundo preset mostra um caso em que o heap sort devolve exatamente o mesmo resultado do estável, por acaso. Código que se apoia nesse acaso passa em todos os testes e quebra quando um dado muda. Se você precisa de ordenação por dois critérios, compare os dois na mesma função de comparação, em vez de ordenar duas vezes.
Heap sort, merge sort ou quick sort
Os três são O(n log n) na média e escolhem-se por outras colunas.
| Algoritmo | melhor | médio | pior | espaço | estável |
|---|---|---|---|---|---|
Heap sort in-place A única linha com teto e piso iguais e sem memória extra. Perde em velocidade real porque salta pelo array e desperdiça cache. | O(n log n) | O(n log n) | O(n log n) | O(1) | não |
Merge sort precisa de array auxiliar Mesma garantia de tempo e estável, ao preço de um array auxiliar. É a escolha quando a estabilidade importa ou os dados não cabem na memória. | O(n log n) | O(n log n) | O(n log n) | O(n) | sim |
Quick sort in-place O mais rápido na média por causa da localidade de memória, mas com um pior caso quadrático que um pivô mal escolhido alcança. | O(n log n) | O(n log n) | O(n²) | O(log n) | não |
Insertion sort in-place Imbatível em array pequeno ou quase ordenado, e é por isso que quase toda biblioteca cai nele abaixo de umas dezenas de elementos. | O(n) | O(n²) | O(n²) | O(1) | sim |
Selection sort in-place É o heap sort sem o heap: mesma ideia de tirar o maior toda rodada, só que procurando com varredura linear em vez de estrutura. | O(n²) | O(n²) | O(n²) | O(1) | não |
Na prática, quase nenhuma biblioteca padrão usa um deles sozinho. O std::sort do C++ implementa introsort: começa com quick sort, troca para insertion sort em trechos pequenos, e cai para heap sort quando a recursão fica funda demais. Ou seja, o heap sort entra ali exatamente como a rede de segurança contra o pior caso quadrático do quick sort. É um ótimo resumo do papel dele: raramente o mais rápido, e o que você quer por perto quando não pode ter uma surpresa ruim.
Um resumo de decisão que funciona:
- Memória apertada e pior caso inaceitável: heap sort.
- Empates precisam manter a ordem original: merge sort, ou qualquer estável.
- Velocidade média e dados na memória: quick sort, com uma boa escolha de pivô.
- Você só precisa dos k maiores, não do array todo: nenhum dos três, use um heap de tamanho k e pare em O(n log k).
Daqui, Dijkstra mostra o heap trabalhando dentro de outro algoritmo em vez de ordenar, e Big O fecha o raciocínio de por que uma soma de O(n) com O(n log n) vira O(n log n). Se a estrutura ainda estiver nebulosa, vale voltar em Binary Heap: o heap sort não tem uma linha que não venha de lá.
Vídeo da aula
Direto do canal da comunidade Craft & Code Club · 2:10:31.
Problemas para praticar
Na ordem em que recomendamos resolver. Marque os que você já fez, fica salvo aqui.
Referências
Artigos e materiais externos para se aprofundar.
Travou em algum passo? Traga sua questão para o Discord da comunidade ou para os encontros semanais.
EntrarEste tópico também tem página própria, fora deste roadmap: Heap Sort.