Heap$-$Build Methods.

$($a$)$ In the top$-$down heap$-$build method, we use MAX$-$HEAP$-$INSERT repeatedly, starting

with an empty heap and inserting from position $1$ to n $,$ resolving the heap structure

by "bubbling up$"$ each new insertion. This means the $2^i$ nodes on level i will each

cause up to i swaps, resulting in the following expression:

total $\frac{?}{?}$# swaps $=(\frac{?}{?}$# nodes $)(\frac{?}{?}$#swaps$)$

$1*0+2*1+2^2*2+$dots$+2^i*i+$dots$+\frac{n}{2}*(logn-1)$

Your task: Argue that the expression on the right side of the inequality is $(nlogn).$

Hint: Lower bound is easy. For the upper bound, exaggerate the amount of bubbling

up to be $logn$ per node.

$($b$)$ In the bottom$-$up heap$-$build method, we use Max$-$Heapify repeatedly from po$-$

sition $n$ to $1,$ resolving the heap structure by "bubbling down" from each position

in turn; however, the first $\frac{n}{2}$ positions are leaves and thus already heaps, so they

cause $0$ swaps. The $\frac{n}{4}$ nodes directly above $($at height $1)$ will each cause up to $1$

swap, and so on$,$ resulting in the following expression:

total $\frac{?}{?}$# swaps $\frac{n}{2}*0+\frac{n}{4}*1+\frac{n}{8}*2+$dots$+\frac{n}{2^k}*(k-1)+$dots$+1*(logn-1)$

We can factor out $n,$ rewriting as:

total $\frac{?}{?}$# swaps $n(\frac{1}{2}*0+\frac{1}{4}*1+\frac{1}{8}*2+$dots$+\frac{1}{2^k}*(k-1)+$dots$+\frac{1}{n}*(logn-1))$

Your task: Argue that the above parenthetical expression is bounded above by a

constant, thus the expression is $(n).$

Hint: One method is the following. First, bound above by the corresponding infinite

series. Try to subtract from the parenthetical expression the sum $\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+$dots

and factor out $\frac{1}{2}.$ Compare the result with the initial expression and figure out what

to do next.