- A afundar
- Comparados
- Trocados
- No lugar
Ordenação por heap
A ordenação por heap (heapsort) lê a lista como uma árvore binária e reorganiza-a num max-heap, em que cada pai é pelo menos tão grande como os filhos. O maior valor fica então no topo. Troque-o para o fim, onde fica, repare o heap e repita. A aplicação desenha o heap como uma árvore por cima das barras, para que possa seguir cada valor enquanto afunda. Prima Reproduzir para ver a ordenação, ou Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto. A árvore por cima das barras mostra os mesmos valores como um heap. Os contadores mostram comparações, trocas e os valores retirados do heap. Escolha quantas barras, como começam, ou escreva os seus próprios números. Com o quadro selecionado, as setas avançam e recuam, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escolha o número de barras e a ordem inicial: aleatória, quase ordenada, invertida ou com poucos valores distintos. Ou escreva os seus próprios números.
- Prima Reproduzir, ou use Avançar e Recuar para ir uma comparação de cada vez. Arraste a barra de passos para saltar para qualquer ponto da ordenação.
- Observe a árvore: primeiro cada pai afunda até o heap estar construído; depois a raiz é trocada para o fim e o heap encolhe uma posição.
Como funciona a ordenação por heap
Leia a lista como uma árvore: o valor na posição i tem os filhos nas posições 2i + 1 e 2i + 2. Construa um max-heap afundando cada pai, a começar pelo último: enquanto um valor for menor do que o seu filho maior, os dois trocam. Quando a raiz tiver o maior valor, troque-o com o último valor do heap. Esse valor fica definitivo, o heap fica uma posição mais curto e a nova raiz afunda para que volte a ser um heap. Repita até o heap ficar vazio.
Sempre n log n, no lugar
A árvore tem cerca de log₂ n níveis, por isso cada afundamento faz no máximo cerca de 2 log₂ n comparações, e a construção do heap menos de 2n. Assim, a ordenação por heap tem um pior caso de cerca de 2n log₂ n comparações, sem buffer: para 40 valores, no máximo 352. Ao contrário do quicksort, não tem entradas más, e ao contrário do merge sort, não precisa de memória extra. Na prática costuma ser mais lenta do que ambos, porque salta de um lado para o outro da lista, e não é estável.
Perguntas frequentes
Como funciona a ordenação por heap?
Transforma a lista num max-heap, uma árvore guardada na lista em que cada pai é pelo menos tão grande como os filhos. Depois, repetidamente, troca o maior valor, na raiz, para o fim do heap e afunda a nova raiz para reparar o heap.
O que é um heap?
Uma árvore binária completa guardada numa lista sem ponteiros: os filhos da posição i são as posições 2i + 1 e 2i + 2. Num max-heap cada pai é pelo menos tão grande como os filhos, por isso o maior valor está sempre na raiz, na posição 0.
Porque é que construir o heap é rápido?
A maioria dos valores está perto da base da árvore e só pode afundar um ou dois níveis. Somando o trabalho em todos os níveis, a construção inteira faz menos de 2n comparações, e não n log n.
A ordenação por heap é estável?
Não. Trocar a raiz para o fim move valores por longas distâncias, por isso valores iguais podem mudar de ordem.
Os meus números são enviados para algum lado?
Não. A ordenação corre no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor