Heap binário: uma fila de prioridades num vetor

Quinze chaves ocupam um vetor que também representa uma árvore: os filhos da posição i estão nas posições 2i + 1 e 2i + 2. Construa um heap inserindo as chaves uma a uma ou começando pelo último pai. Acompanhe as comparações e as trocas, extraia a menor chave e veja a seguinte subir.

Exemplo resolvido — Heap binário: uma fila de prioridades num vetor

Chaves	15
Construção por inserções sucessivas	34 comparações, 34 trocas
Máximo de comparações por inserções sucessivas	34
Construção a partir do último pai	22 comparações, 11 trocas
Máximo de comparações a partir do último pai	22

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Lição

A teoria — Heap binário: uma fila de prioridades num vetor

Um heap mínimo binário é um vetor em que a chave de cada posição i é menor ou igual às chaves das posições 2i + 1 e 2i + 2, os seus filhos; o pai da posição i está em ⌊(i − 1) / 2⌋. Assim interpretado, o vetor representa uma árvore binária completa. A menor chave está sempre na posição 0, a raiz. Para inserir uma chave, coloque-a no fim e faça-a subir, trocando-a com o pai enquanto for menor do que ele. Para extrair a menor chave, passe a última para a raiz e faça-a descer, trocando-a com o menor dos filhos enquanto esse filho for menor do que ela. Um heap usado desta forma é uma fila de prioridades.

O que significa cada símbolo

n: número de chaves no heap
i: posição no vetor, a contar de 0
h: altura de uma posição: número de níveis abaixo dela, ⌊log₂(n / (i + 1))⌋

Pressupõe: Uma comparação confronta uma chave com outra; uma troca permuta as chaves de duas posições. Passar a última chave para a raiz durante uma extração não conta como nenhuma destas operações. Uma chave igual ao pai ou ao menor dos filhos fica onde está. Se os filhos forem iguais, escolhe-se o da esquerda. Este heap mantém a menor chave na raiz; num heap máximo, inverte-se o sentido de todas as comparações. A ferramenta permite até quinze chaves, de 0 a 99, para que a árvore inteira caiba no ecrã de um telemóvel. As permutações contadas na última linha são de chaves distintas.

A inserção depende da profundidade; a construção a partir do último pai, da altura 🖖

Prima Decrescente, uma a uma. Cada nova chave é menor do que todas as que já estão no heap, por isso sobe até à raiz, com uma comparação e uma troca por nível: 0 para a raiz, 1 para cada uma das duas posições seguintes, 2 para cada uma das quatro seguintes e 3 para cada uma das últimas oito. O total é 34. Prima agora Decrescente, último pai. As mesmas quinze chaves são colocadas no vetor pela ordem de chegada. A seguir, fazem-se descer as chaves das posições com filhos, de 6 até 0. Cada chave só pode descer tantos níveis quantos os que tem abaixo de si. Oito das quinze posições são folhas: aquelas que exigiram três níveis de subida no primeiro método não dão trabalho neste. A soma das alturas é 11; com duas comparações por nível, obtêm-se 22. Em qualquer heap, a soma das alturas é n menos o número de algarismos 1 na representação binária de n, pelo que esta construção exige sempre menos de 2n comparações. Com 1.023 chaves por ordem decrescente, os dois métodos exigem 8.194 e 2.026.

Por ordem crescente, os dois métodos exigem as mesmas 14 comparações 🖖

Prima Crescente, uma a uma. Cada nova chave já é maior ou igual ao pai: basta uma comparação, sem troca, num total de 14. Escolha A partir do último pai e voltará a obter 14. Cada pai compara os filhos entre si e depois compara-se com o menor deles, ficando onde está. O mínimo para ambos os métodos é 14, pois todas as chaves, exceto a raiz, têm de ser comparadas pelo menos uma vez. Acima desse mínimo, o custo dos métodos começa a divergir; a ordem decrescente leva a inserção uma a uma ao seu máximo. Quando as chaves estão baralhadas, o custo fica muito mais perto do mínimo. Em 200 baralhamentos de 1.000 chaves, a inserção uma a uma exigiu, em média, 2.235 comparações, e a construção a partir do último pai, 1.862. A inserção das mesmas chaves por ordem decrescente exige 7.987. Com quinze chaves, a diferença é pequena: prima Baralhar algumas vezes e verá que, por vezes, a inserção uma a uma ganha.

Um heap está longe de estar ordenado 🖖

Num heap, nenhuma chave é maior do que os seus filhos. Das 5.040 permutações de sete chaves distintas, 80 cumprem essa condição. A menor chave tem de estar na raiz. Quaisquer três das outras seis podem formar a subárvore esquerda, e cada subárvore tem também de ser um heap. O número de possibilidades é 7! dividido pelo produto dos tamanhos de todas as subárvores, 7 · 3 · 3. Para quinze chaves, a tabela de resultados mostra 21.964.800 heaps entre 1.307.674.368.000 permutações; só uma está ordenada. Esta liberdade torna a construção de um heap pouco dispendiosa. Para obter as chaves por ordem, prima Heapsort. A cada extração da raiz, a última chave sobe para ocupar o lugar vazio e depois desce, deixando a menor das chaves restantes na raiz. As doze chaves saem por ordem: 3, 7, 12 e assim por diante, até 93.

Problema resolvido na íntegra

Quantas comparações exige cada método com mil chaves? 4 passos
Prima Decrescente, uma a uma e depois Decrescente, último pai. Explique os valores 34 e 22. Considere agora 1.023 chaves que chegam por ordem decrescente. Quantas comparações faz cada método?

Abrir este problema na ferramenta
1. A posição i tem profundidade ⌊log₂(i + 1)⌋: uma posição à profundidade 0, duas à profundidade 1, quatro à profundidade 2 e oito à profundidade 3. Por ordem decrescente, cada nova chave é a menor até ao momento e sobe até à raiz, com uma comparação e uma troca por nível: 0 + 2 · 1 + 4 · 2 + 8 · 3 = 34.
  
  $0 + 2 \cdot 1 + 4 \cdot 2 + 8 \cdot 3 = 34$
2. Na construção a partir do último pai, conta a altura: 3 para a raiz, 2 para as posições 1 e 2, 1 para as quatro posições à profundidade 2 e 0 para as oito folhas. A soma é 11. Por ordem decrescente, cada chave desce até ao fundo. Com quinze chaves, todos os pais têm dois filhos, pelo que cada nível exige duas comparações: 22 comparações e 11 trocas.
  
  $3 + 2 \cdot 2 + 4 \cdot 1 = 11, 2 \times 11 = 22$
3. 1.023 = 2¹⁰ − 1 corresponde a uma árvore perfeita com dez níveis e 2ᵈ posições à profundidade d. Na inserção uma a uma, o número de comparações é a soma das profundidades: 1 · 2 + 2 · 4 + 3 · 8 + ⋯ + 9 · 512 = 8.194. Há outras tantas trocas.
  
  $d = 0 \sum 9 d \cdot 2^{d} = 8 \cdot 2^{10} + 2 = 8194$
4. A construção a partir do último pai exige o dobro da soma das alturas. Há 2⁹ posições de altura 0, 2⁸ de altura 1, e assim sucessivamente até à raiz, de altura 9: 1 · 256 + 2 · 128 + ⋯ + 9 · 1 = 1.013. Este valor é 1.023 menos os dez algarismos 1 da sua representação binária. O dobro dá 2.026 comparações, com 1.013 trocas.
  
  $h = 0 \sum 9 h \cdot 2^{9 - h} = 1023 - 10 = 1013, 2 \times 1013 = 2026$
Resposta

8.194 comparações na inserção uma a uma e 2.026 na construção a partir do último pai: cerca de oito por chave no primeiro método e duas no segundo. A maioria das posições de um heap tem grande profundidade e pequena altura. O custo da inserção depende da profundidade; o da construção a partir do último pai depende da altura. A ferramenta admite até quinze chaves, para as quais o mesmo cálculo dá os valores 34 e 22 apresentados.

$8194 against 2026$

Percurso de aprendizagem

O que custa pouco numa estrutura de dados

Referências (2)

Heapsort as first published: J. W. J. Williams, "Algorithm 232: Heapsort," Communications of the ACM 7(6), 347–348, June 1964.
The heap-based sort published six months later, close to the version used today: Robert W. Floyd, "Algorithm 245: Treesort 3," Communications of the ACM 7(12), 701, December 1964.

Pela equipa 42Math · Verificado com fontes publicadas. Correções bem-vindas.