0
$\begingroup$

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)
$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.