Heapsort
Organiza a lista em um heap, uma árvore em que cada pai é maior que seus filhos. Depois leva o maior valor para o fim, repetidas vezes.
- melhor caso Ω(n log n)
- caso médio Θ(n log n)
- pior caso O(n log n)
- memória O(1)
- não estável
- sem memória extra
O que significam esses termos?
- Melhor caso: como o tempo cresce com o tamanho n da lista quando a entrada é a mais fácil para este algoritmo.
- Caso médio: como o tempo costuma crescer com n. Com n², o dobro de valores leva cerca de quatro vezes mais tempo; n log n cresce bem menos.
- Pior caso: o crescimento com a entrada mais difícil. Útil quando a velocidade nunca pode cair.
- Memória: quanta memória extra é necessária além da lista. 1 significa algumas variáveis; n, uma cópia da lista.
- Estável: dois valores iguais mantêm a ordem original. Importa ao ordenar por um só campo de um registro.
- Sem memória extra: ordena dentro da própria lista, sem uma segunda lista.
- comparando
- movendo
- na posição final
Clique em reproduzir: as linhas mostram como o custo cresce
Clique em reproduzir ou avance passo a passo pelo algoritmo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: pular.
Experimente: Escolha uma lista invertida. Montar o heap quase não exige trocas; depois, cada rodada leva o maior valor para o fim.
Como funciona
O heap fica guardado na própria lista: o valor na posição i tem os filhos nas posições 2i+1 e 2i+2, e o maior valor fica sempre na frente. Ele é trocado com o do fim, o heap diminui uma posição e é consertado. A parte ordenada cresce a partir da direita.
Quando é uma boa escolha
Quando você precisa de uma velocidade que continua boa mesmo no pior caso, sem memória extra, por exemplo em aparelhos pequenos. Em média é mais lento que o quicksort, por isso costuma ser usado como plano B.