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:
  1. 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.
  2. Satisfaz a propriedade de heap (max-heap ou min-heap):
  • No max-heap, para todo nó i (exceto a raiz), vale
A[\lfloor i/2\rfloor] \ge A[i].
  • No min-heap, vale
A[\lfloor i/2\rfloor] \le A[i].
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):
  1. Representamos a árvore em um vetor A[1..n] em nível-por-nível.
  2. Começamos do último nó que tem filho, isto é, do índice \lfloor n/2\rfloor, e seguimos até 1.
  3. Para cada índice i de \lfloor n/2\rfloor até 1, aplicamos o procedimento sift-down (ou heapify): comparamos A[i] com seus filhos, trocamos com o maior filho (em max-heap) se necessário e continuamos recursivamente na subárvore afetada.
  4. Esse processo garante, ao final, que todo sub-vetor enraizado em i satisfaça a propriedade de heap.
    A complexidade desse build-heap é O(n), 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):
  1. Depois de construir um max-heap em O(n), o maior elemento está em A[1].
  2. Para extrair esse máximo e colocá-lo na posição final do vetor, trocamos A[1] com A[n], reduzimos o tamanho efetivo do heap para n-1 e reaplicamos sift-down na raiz em O(\log n).
  3. Repetindo essa extração n vezes, obtemos o vetor completamente ordenado em ordem crescente.
  4. O custo total do heapsort é
O(n) + n \cdot O(\log n) = O(n\log n),
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 \lfloor n/2\rfloor até 1 em O(n). Em ordenação (heapsort), heaps permitem extrair sucessivamente o maior (ou menor) elemento em O(\log n) cada, resultando em O(n\log n) de tempo e uso constante de espaço extra.

Exercícios de Livros Relacionados