Heap, fila de prioridade e ordenação
Ordenar é uma das tarefas mais comuns da computação, e existem dezenas de jeitos de fazê-la. Hoje vamos ver os clássicos, entender por que alguns são O(n²) e outros O(n log n), conhecer o heap e descobrir como ordenar sem comparar.
Navegação: ← → trocam de etapa · V alterna entre etapas e página única · M sumário · F tela cheia · + − tamanho do texto · dentro do código, Ctrl+Enter executa.
Todo código desta aula pode ser editado e executado aqui mesmo. Altere os exemplos à vontade; o botão ↺ restaura o original. Suas alterações ficam salvas neste navegador; em Progresso você pode baixá-las em um arquivo e continuar em outro computador.
As visualizações mostram os algoritmos passo a passo: altere os dados, use Próximo passo ou Animar. Nos exercícios, o botão ✓ Verificar testa seu código com várias entradas.
Ordenar e priorizar
Dados ordenados tornam muitas tarefas fáceis: busca binária, encontrar repetidos (ficam vizinhos), mediana, ranking, intercalar relatórios…
Às vezes não precisamos de tudo ordenado, só de saber quem é o próximo: o paciente mais grave, o processo mais urgente, o evento mais cedo. Para isso existe a fila de prioridade.
Ao longo da aula, conte as comparações: é a medida que usamos para comparar algoritmos de ordenação.
Fila de prioridade
Uma fila de prioridade guarda elementos com uma prioridade e oferece três operações: inserir, ver o topo (o de maior prioridade) e remover o topo.
Aplicações: triagem de pronto-socorro, escalonador de processos do sistema operacional, simulação de eventos, o algoritmo de Dijkstra (aula de grafos), compressão de Huffman.
| Implementação | inserir | remover topo |
|---|---|---|
| lista sem ordem | O(1) | O(n): procura o maior |
| lista ordenada | O(n): desloca | O(1): pop() |
| heap | O(log n) | O(log n) |
Heap binário: uma árvore guardada em vetor
Um heap máximo é uma árvore binária quase completa (níveis cheios, o último preenchido da esquerda para a direita) em que todo pai é maior ou igual aos filhos. O maior fica na raiz.
Como a árvore é quase completa, ela cabe num vetor sem buracos, nível por nível. Não precisamos de ponteiros: as posições se calculam.
Altura de um heap com n elementos: ⌊log₂ n⌋. É isso que garante O(log n) nas operações.
Inserir: o novo elemento sobe
- Coloque o elemento no fim do vetor (próxima folha livre).
- Enquanto ele for maior que o pai, troque com o pai (sift up).
Ele sobe no máximo a altura da árvore: O(log n).
Remover o topo: a raiz desce
- Guarde o topo
h[0]. - Coloque o último elemento na raiz e remova a última posição.
- Enquanto a raiz for menor que algum filho, troque com o maior filho (sift down).
Por que o maior filho? Ele vai virar pai do outro, então precisa ser maior que ele.
Custo: O(log n).
Construir um heap em O(n)
Inserir n elementos um a um custa O(n log n). Dá para fazer melhor: as folhas (metade do vetor) já são heaps; basta descer cada nó interno, do último para a raiz.
Metade dos nós são folhas e não descem; um quarto desce no máximo 1 nível; um oitavo, 2 níveis… A soma n/4·1 + n/8·2 + n/16·3 + … é menor que n: O(n).
O módulo heapq
O Python já traz um heap pronto, que trabalha sobre uma list comum. Atenção: é um heap mínimo (o menor fica em h[0]).
| Função | O que faz | Custo |
|---|---|---|
heappush(h, x) | insere | O(log n) |
heappop(h) | remove e devolve o menor | O(log n) |
h[0] | espia o menor | O(1) |
heapify(v) | transforma a lista em heap | O(n) |
nlargest(k, v) | os k maiores | O(n log k) |
Para um heap máximo, guarde os valores negativos. Para prioridades com dados, use tuplas (prioridade, item): tuplas se comparam pelo primeiro elemento.
Heapsort
Construa um heap máximo com o vetor e repita: troque o topo (o maior) com o último elemento do heap, encolha o heap e desça a nova raiz. O vetor fica ordenado no próprio lugar.
Custo: construir O(n) + n remoções de O(log n) = O(n log n) sempre, mesmo no pior caso. Memória extra: O(1).
Desvantagens: não é estável e, na prática, costuma ser mais lento que o quick sort, porque salta pela memória.
Bubble sort
Percorra o vetor comparando vizinhos e trocando os que estão fora de ordem. A cada passada, o maior dos restantes “borbulha” até o fim.
Pior caso (vetor invertido): n(n−1)/2 comparações e trocas: O(n²).
Com a parada antecipada (“nenhuma troca na passada”), o melhor caso (já ordenado) é O(n).
Selection sort
Para cada posição i, procure o menor elemento do trecho restante e troque-o com v[i].
Sempre n(n−1)/2 comparações, qualquer que seja a entrada: O(n²) no melhor e no pior caso.
Em compensação, faz no máximo n − 1 trocas. Útil quando escrever na memória é muito caro.
Insertion sort
Como organizar cartas na mão: pegue o próximo elemento e insira-o no lugar certo do trecho já ordenado à esquerda, deslocando os maiores.
Pior caso (invertido): O(n²). Melhor caso (ordenado): só n − 1 comparações, O(n).
Em vetores quase ordenados ou pequenos, é excelente. Por isso aparece dentro de algoritmos “de verdade”, como o Timsort do Python.
Teste de mesa do insertion sort
Acompanhe como x guarda o elemento enquanto os maiores andam para a direita. Antes de avançar, preveja o próximo valor de v.
Comparando as ordenações simples
| Algoritmo | Melhor | Pior | Trocas | Estável? |
|---|---|---|---|---|
| bubble | O(n) | O(n²) | até n²/2 | sim |
| selection | O(n²) | O(n²) | até n − 1 | não |
| insertion | O(n) | O(n²) | até n²/2 | sim |
Um algoritmo é estável quando elementos com a mesma chave mantêm a ordem original. Importa ao ordenar por um critério e depois por outro (ex.: por nome, depois por turma).
No exemplo, o selection sort inverte a ordem original de dois alunos com nota 7.
Intercalar duas listas ordenadas
A peça central do merge sort: juntar duas listas já ordenadas em uma só, comparando apenas os primeiros elementos ainda não usados de cada uma.
Cada comparação coloca um elemento no resultado; quando uma lista acaba, o resto da outra é copiado. Custo O(n + m).
Usar <= (e não <) no empate pega primeiro da lista da esquerda: é isso que torna o merge sort estável.
Merge sort
Dividir e conquistar: divida o vetor ao meio, ordene cada metade (recursivamente) e intercale as duas. Um vetor de 0 ou 1 elemento já está ordenado.
As divisões formam log₂ n níveis. Em cada nível, as intercalações juntas processam os n elementos. Total: O(n log n), em qualquer caso.
Custo extra: precisa de O(n) de memória auxiliar para intercalar. É estável.
Partição: a ideia do quick sort
Escolha um pivô e reorganize o vetor para que os menores fiquem à esquerda dele e os maiores à direita. O pivô termina na sua posição definitiva.
Partição de Lomuto (pivô = último): o índice j examina cada elemento; i marca onde termina a parte dos menores. Uma passada: O(n), sem memória extra.
Quick sort e a escolha do pivô
Particione e ordene recursivamente os dois lados. Se o pivô divide o vetor em partes parecidas, são log n níveis de O(n): O(n log n) em média, e muito rápido na prática.
Mas com o pivô no último elemento e o vetor já ordenado, cada partição só tira um elemento: n níveis, O(n²) e recursão profunda.
Solução comum: escolher o pivô aleatoriamente (ou a mediana de três). O pior caso continua existindo, mas fica improvável.
Comparando os tempos
Medindo de verdade, dobrando n: os quadráticos quadruplicam; os O(n log n) pouco mais que dobram.
| Algoritmo | Médio | Pior | Memória | Estável |
|---|---|---|---|---|
| insertion | O(n²) | O(n²) | O(1) | sim |
| merge sort | O(n log n) | O(n log n) | O(n) | sim |
| quick sort | O(n log n) | O(n²) | O(log n) | não |
| heapsort | O(n log n) | O(n log n) | O(1) | não |
Desafio: o k-ésimo menor (quickselect)
Para achar a mediana não é preciso ordenar tudo. Depois de uma partição, o pivô está na posição definitiva p:
- se
p == k, achou; - se
k < p, continue só no lado esquerdo; - senão, só no direito.
Só um lado é visitado a cada vez: em média n + n/2 + n/4 + … = O(n).
Complete k_esimo(v, k) (k começa em 0) e teste com a mediana.
Mostrar uma solução
O limite das comparações: Ω(n log n)
Todo algoritmo que ordena só comparando elementos precisa, no pior caso, de pelo menos log₂(n!) comparações.
Por quê? Existem n! ordens possíveis da entrada, e cada comparação tem só duas respostas (sim/não). Com k comparações distinguimos no máximo 2ᵏ casos; precisamos de 2ᵏ ≥ n!.
E log₂(n!) cresce como n log₂ n. Portanto merge sort e heapsort são ótimos entre os algoritmos por comparação.
Para ir além, é preciso não comparar: usar os próprios valores como índices.
Counting sort: contar em vez de comparar
Se os valores são inteiros entre 0 e k, conte quantas vezes cada um aparece e escreva-os em ordem.
Custo O(n + k): uma passada nos dados e uma no vetor de contagem. Com k pequeno (notas de 0 a 10, idades, dias do mês), é linear.
Com k enorme (ex.: CPFs), o vetor de contagem fica gigante: não serve.
A versão com somas acumuladas (ao lado) calcula a posição final de cada valor e é estável, o que permite ordenar registros por uma chave.
Radix sort: um dígito por vez
Ordene pelo dígito das unidades, depois das dezenas, depois das centenas… usando, em cada passada, uma distribuição estável em 10 baldes.
Com d dígitos, são d passadas de O(n + 10): O(d · n). Funciona para números grandes sem um vetor de contagem gigante, e para textos de tamanho fixo (CEPs, placas, datas AAAAMMDD).
A estabilidade é essencial: ao ordenar pelas dezenas, os empates mantêm a ordem já obtida pelas unidades.
Na prática: sorted() e list.sort()
No dia a dia, use o que o Python oferece: o Timsort, um híbrido de merge sort e insertion sort que aproveita trechos já ordenados. É O(n log n), O(n) em dados quase ordenados, e estável.
sorted(v)devolve uma lista nova;v.sort()ordena a própria lista e devolveNone.key=diz por qual valor comparar;reverse=Trueinverte.- Para vários critérios, a chave pode ser uma tupla, ou ordene em etapas aproveitando a estabilidade.
Qual algoritmo?
Leia a situação, discuta com a turma e só então clique.
Qual será a saída?
Leia o código, escreva sua resposta e só então clique. Errou? Copie o código para o laboratório e execute.
Prática 1: heap e insertion sort
Escreva sua solução no editor. ▶ Executar roda com a entrada que você quiser; ✓ Verificar roda os testes automáticos e mostra o que falta. Tente antes de abrir a solução!
1. É um heap máximo? básico
Leia números inteiros na mesma linha (um vetor) e mostre É heap máximo se todo elemento for menor ou igual ao seu pai, ou Não é heap caso contrário.
| Entrada | Saída esperada |
|---|---|
9 7 8 3 5 6 | É heap máximo |
9 7 8 3 10 | Não é heap |
Mostrar uma solução
2. Insertion sort passada a passada básico
Leia números inteiros na mesma linha e ordene-os com insertion sort. Depois de inserir cada elemento i (de 1 até n − 1), mostre Passada i: [lista]. No fim, mostre Ordenado: [lista]. Não use sort() nem sorted().
| Entrada | Saída esperada |
|---|---|
5 2 4 1 | Passada 1: [2, 5, 4, 1] Passada 2: [2, 4, 5, 1] Passada 3: [1, 2, 4, 5] Ordenado: [1, 2, 4, 5] |
Mostrar uma solução
Prática 2: heapq e intercalação
Dois problemas clássicos em que não é preciso ordenar tudo de novo.
3. Os k maiores médio
Leia números inteiros na primeira linha e um inteiro k na segunda. Mostre os k maiores em ordem decrescente, separados por espaço: Maiores: a b c. Se k for maior que a quantidade de números, mostre todos.
Use heapq mantendo um heap mínimo com no máximo k elementos: O(n log k), sem ordenar a lista toda.
| Entrada | Saída esperada |
|---|---|
5 1 9 3 7 2 3 | Maiores: 9 7 5 |
Mostrar uma solução
4. Intercalar e contar médio
Leia duas listas de inteiros em ordem crescente (uma por linha; uma linha pode estar vazia). Intercale-as sem usar sort() ou sorted() e mostre Intercalada: [lista] e Comparações: c, contando só as comparações feitas enquanto as duas listas ainda têm elementos. No empate, pegue da primeira lista.
| Entrada | Saída esperada |
|---|---|
1 4 7 2 3 8 9 | Intercalada: [1, 2, 3, 4, 7, 8, 9] Comparações: 5 |
Mostrar uma solução
Prática 3: merge sort e contagem
O primeiro reaproveita o merge sort para responder outra pergunta; o segundo dispensa comparações.
5. Contar inversões desafio
Uma inversão é um par de posições i < j com v[i] > v[j]; mede o quão desordenado está o vetor. Leia inteiros na mesma linha e mostre Inversões: k.
Testar todos os pares é O(n²). Adapte o merge sort: ao intercalar, quando um elemento da metade direita sai antes, ele forma inversão com todos os que ainda restam na metade esquerda. Assim fica O(n log n).
| Entrada | Saída esperada |
|---|---|
2 4 1 3 5 | Inversões: 3 |
Mostrar uma solução
6. Notas por contagem médio
Leia notas inteiras de 0 a 10 na mesma linha. Usando counting sort (um vetor de 11 contadores, sem sort()), mostre Ordenadas: … (separadas por espaço) e Moda: x, a nota mais frequente. No empate, a menor nota.
| Entrada | Saída esperada |
|---|---|
7 3 10 7 0 3 7 | Ordenadas: 0 3 3 7 7 7 10 Moda: 7 |
Mostrar uma solução
Laboratório livre
Espaço para testar ideias durante a aula. Sugestões: implemente um heap mínimo trocando as comparações do heap máximo; conte as comparações do merge sort e compare com n log₂ n; ordene uma lista de palavras pelo tamanho e, no empate, em ordem alfabética.