Defina um heap e explique como as árvores podem ser transformadas em heaps. Por que os heaps são úteis em ordenação?
Passo 1
O enunciado pede para definirmos o que é um heap, mostrarmos como transformar uma árvore binária (ou um vetor) em heap e explicarmos por que heaps são úteis em ordenação. O conteúdo envolve estruturas de dados (heap) e o algoritmo de construção de heap (heapify), com aplicação no heapsort.
Passo 2
Definição de heap:
- Um heap é uma árvore binária completa (ou quase completa), isto é, todos os níveis, exceto talvez o último, estão totalmente preenchidos, e as folhas do último nível estão alinhadas à esquerda.
- Satisfaz a propriedade de heap (max-heap ou min-heap):
- No max-heap, para todo nó
(exceto a raiz), vale
- No min-heap, vale
Em ambos os casos, o elemento de maior prioridade (máximo ou mínimo) fica na raiz.
Passo 3
Transformando uma árvore/vetor arbitrário em heap (algoritmo build-heap):
- Representamos a árvore em um vetor
em nível-por-nível. - Começamos do último nó que tem filho, isto é, do índice
, e seguimos até . - Para cada índice
de até , aplicamos o procedimento sift-down (ou heapify): comparamos com seus filhos, trocamos com o maior filho (em max-heap) se necessário e continuamos recursivamente na subárvore afetada. - Esse processo garante, ao final, que todo sub-vetor enraizado em
satisfaça a propriedade de heap.
A complexidade desse build-heap é, pois cada chamada a sift-down faz, no pior caso, um número de trocas proporcional à altura do nó, e a soma amortizada sobre todos os nós é linear.
Passo 4
Por que heaps são úteis em ordenação (heapsort):
- Depois de construir um max-heap em
, o maior elemento está em . - Para extrair esse máximo e colocá-lo na posição final do vetor, trocamos
com , reduzimos o tamanho efetivo do heap para e reaplicamos sift-down na raiz em . - Repetindo essa extração
vezes, obtemos o vetor completamente ordenado em ordem crescente. - O custo total do heapsort é
sem necessidade de espaço auxiliar além do vetor original (é in-place).
Resposta
Um heap é uma árvore binária quase completa que satisfaz a propriedade de heap (pai ≥ filho em max-heap). Para transformá-la em heap usa-se o algoritmo build-heap, que aplica sift-down de
até
em
. Em ordenação (heapsort), heaps permitem extrair sucessivamente o maior (ou menor) elemento em
cada, resultando em
de tempo e uso constante de espaço extra.