Running Build-Heap Algorithm on given numbers

Question

I don't fully understand this build-heap function. Lets assume we have array 3, 4, 5, 13, 16, 32.

It seems like we swap the parent when it is less than the current A[j] but which number does the loop start with? Maybe somebody can go through 2-3 loops and show how the array changes after 1st loop, 2nd loop, 3rd loop. Much appreciated. Oh, also, what would be the runtime?

for i=2 to n
    j = i
    while (j>1) and A[parent(j)]<A[j] do
        swap A(parent(j)] and A[j]
        j = parent(j)

Answer 1

It appears you're building a max-heap, where every element is greater than or equal to its child elements (if any). With that understanding, let's trace the action. First, the parent node of $A[j]$ will be $A[j/2]$ (integer division: discard any remainder) so we'll have $$\begin{array}{r|cccccccc} j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \dotsc\\ parent(j) & \_ & 1 & 1 & 2 & 2 & 3 & 3 & \dotsc \end{array}$$ To keep things simple, we'll let the initial array be $[3,4,5,13]$:

Insert at $i=2$.

$A[parent(2)]=A[1]=3 < 4=A[2]$ so we swap $A[1]$ and $A[2]$, giving us the array $$ [4,3,5,13] $$

Insert at $i=3$.

$A[parent(3)]=A[1]=4 < 5=A[3]$ so we swap $A[1]$ and $A[3]$, giving us the array $$ [5,3,4,13] $$

Insert at $i=4$.

$A[parent(4)]=A[2]=3 < 13=A[4]$ so we swap $A[2]$ and $A[3]$, giving us the array $$ [5,13,4,3] $$ and now $j=parent(4)=2>1$ so we see if we need another swap.

$A[parent(2)]=A[1]=5 < 13=A[2]$ so we swap $A[1]$ and $A[2]$, giving us the array $$ [13,5,4,3] $$ and we're done, the array is now a max-heap.

---

The runtime of this algorithm is no worse than a multiple of $n\log n$ since none of the elements are further than $\log_2n$ from the root at $i=1$ so you'll need at most $\log n$ swaps for each of the $n$ elements. This, by the way, is not as good as possible: there's different algorithm that builds a heap in no more than a multiple of $n$ time.