A linear time algorithm

The linear time algorithm I'm about to present also traverses the tree underlying the heap, and does work at each node, but does so from the bottom up.

def heapify(A, i):
    l = left_child(i)
    r = right_child(i)
    if A[l] > A[r] and A[l] > A[i]:
        # swap A[l] and A[i]
        heapify(A, l)
    elif A[r] > A[l] and A[r] > A[i]:
         # swap A[r] and A[i]
         heapify(A, r)

def build_heap();
    for i in range(len(A)/2, 0, -1):
        heapify(A,i)

Proof of correctness

(TODO)

Runtime analysis

For the analysis that follows it will be most convenient if we consider the leaves of the tree level $0$, and the root of the tree level $h$ (where $h = \log n$ is the total height of the tree). Note that $n = 2^h$, so it will suffice to show that $t_{buildheap}(n) = O(2^h)$.

\begin{align} t_{build heap}(n) &= \sum_{i=len(A)/2}^{0} t_{heapify}(i) \notag \\ &\leq \sum_{i=0}^{n-1} t_{heapify}(i) \notag \\ &= \sum_{\ell = 0}^h \sum_{i \in Level(\ell)} t_{heapify}(i) \notag \\ &= \sum_{\ell = 0}^h |Level(\ell)| \ell \notag \\ &= \sum_{\ell=0}^h 2^{h - \ell} \ell \label{eq:tut_mistake_1} \\ &= 2^h \sum_{\ell=0}^h \ell/2^{\ell} \label{eq:tut_mistake_2} \\ &\leq 2^h \sum_{\ell = 0}^\infty \ell/2^{\ell} \notag \\ \end{align}

The course text cites that \begin{equation} \label{eq:geometric_series_derivative} \sum_{\ell \geq 0} \ell / 2^{\ell} = O(1) \end{equation} which is enough to finish the proof (giving us that $t_{build heap}(n) = O(2^h) = O(n)$. But the derivation of \eqref{eq:geometric_series_derivative} is nice enough, so we'll do it here.

Proposition

If $x \in (0,1)$ then \[ \sum_{i=0}^\infty i x^i = x(1 - x)^{-2} \] Applying this proposition for $x = 1/2$ this gives that $\sum_\ell \ell/2^\ell = 2 = O(1)$ as required.

Proof

Recall that for $x \in (0,1)$ \[ \sum_{i=0}^\infty x^i = (1-x)^{-1} \] This formula is the really the workhorse. We just have to identify it in the expansion of $\sum_i ix^i$. So let's look: \begin{align*} \sum_i ix^i &= x + 2x^2 + 3x^3 + \ldots \\ &= x(1 + 2x + 3x^2 + \ldots ) \\ &= x \left( \frac{d}{dx} (1 + x + x^2 + x^3 + \ldots) \right) \\ &= x \left( \frac{d}{dx} (1 - x)^{-1} \right) & \mbox{(necessites $x \in (0,1)$)} \\ &= x (1- x)^{-2} \end{align*}

Notes

During tutorial, in my haste, I expanded \eqref{eq:tut_mistake_1} as $2^h + \sum_\ell \ell/2^\ell$ rather than \eqref{eq:tut_mistake_2}. D'oh!