CCM0128 - Computação II (2025i)

Um fato interessante que vimos sobre a montagem do heap na primeira fase do heapsort é que aquela fase faz menos de $2N$ comparações e menos $N$ trocas, onde $N\geq1$ é número de elementos no vetor sendo ordenado. Assim, essa primeira fase tem complexidade $O(N)$. Veja a página 44 de

https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/24PriorityQueues.pdf

Ao concluir esse exercício, você saberá justificar a proposição na página indicada acima para todo valor de $N$ e não apenas para $N$ da forma $2^{h+1}-1$.

Lembre que heaps têm por base árvores binárias completas (ABCs): árvores binárias (ABs) cujos níveis são completos, a menos possivelmente do último nível, que está preenchido "da esquerda para a direita". Um fato crucial é que a altura média dos nós em uma ABC é no máximo $1$.

Altura de nós em ABs.  Em uma AB, cada nó \(x\) é a raiz de uma subárvore: a subárvore "enraizada em $x$". Definimos a altura $h(x)$ de $x$ como sendo a altura dessa subárvore enraizada em $x$.  Assim, por exemplo, $h(x)=0$ se $x$ é uma folha (isto é, não tem filhos) e se um nó $x$ não é folha mas só tem folhas como filhos, então $h(x)=1$.

Seja $T$ uma ABC. Estamos interessados em determinar ou estimar a soma

\( S=\sum_xh(x), \)

onde a soma estende-se sobre todo nó $x$ de $T$.  Por exemplo, no caso da ABC na página 44 das transparências de S&W, temos que $S=11$.

Preliminares.  Seja $N\geq1$ um inteiro e suponha que a representação binária de $N$ seja $(b_nb_{n-1}\dots b_0)_2$. Temos então $b_n=1$ e $n=\lfloor\lg N\rfloor$. Escrevemos

\( N=(b_n\dots b_0)_2. \)

Seja $T$ uma ABC com $N$ nós. Sejam $T_1$ e $T_2$ as subárvores esquerda e direita de $T$. Sejam $N_1$ o número de nós em $T_1$ e $N_2$ o número de nós em $T_2$.

(1) Prove que se $b_{n-1}=1$, então $N_1=2^n-1$ e $N_2=(b_{n-1}\dots b_0)_2$.

(2) Prove que se $b_{n-1}=0$, então $N_1=(1b_{n-2}\dots b_0)_2$ e $N_2=2^{n-1}-1$.

Soma das alturas dos nós em uma ABC.  Seja $T$ uma ABC com $N$ nós. Seja $u_N$ o número de bits $1$ na representação binária de $N=(b_n\dots b_0)_2$, isto é, $u_N=|\{i:b_i=1\}|$. Seja $S$ a soma das alturas de todos os nós em $T$.

(3) Prove que $S=N-u_N$.

(4) Deduza a proposição na página 44 de https://www.ime.usp.br/~yoshi/Sedgewick/Algs4th/Slides/24PriorityQueues.pdf (note que sua demonstração deve valer para todo $N\geq1$).

Observações 

1. Seque de (3) que $S/N<1$, isto é, a altura média dos nós em uma ABC é menor que $1$.
2. A profundidade de um nó $x$ em uma AB $T$ é definida como sua distância à raiz de $T$. Assim, a raiz de $T$ tem profundidade $0$, os filhos da raiz têm profundidade $1$, os netos têm profundidade $2$, etc. Em um possível exercício teórico futuro, você provará que, em qualquer árvore binária $T$ com $N$ nós, a profundidade média dos nós em $T$ é pelo menos $\sim\lg N$.