Comparações
Trocas
Extraídos

  • A afundar
  • Comparados
  • Trocados
  • No lugar

Mais sobre a ordenação por heap

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

  1. 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.
  2. 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.
  3. 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