Cheap and Secure Web Hosting Provider : See Now

heapify last 3 lines

, , No Comments
Problem Detail: 

I'm following http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec04.pdf

Last 3 lines of heapify pseudocode are:

if largest =! i     then exchange A[i] and A[largest]     Max_Heapify(A, largest) 

What is the aim of the last line? Since largest still holds value of largest leaf, which is now root, what would the recursive run achieve? Just an empty run, it seems.Max-heap is already built.

Asked By : kaboom

Answered By : Yuval Filmus

You are asking several related questions. I will only answer the first one. The heapify procedure gets an almost-heap $A$ and a node $i$. The heap property is satisfied for all nodes except for $i$. Heapify proceeds as follows:

  1. Determine the largest child $j$ of $i$.
  2. If $A[i] \geq A[j]$, the heap property is already satisfied.
  3. Otherwise, exchange $A[i]$ and $A[j]$, and run heapify on $A$ and $j$.

After the exchange, the heap property is no longer violated for $i$, but might be violated for $j$. For this reason we have to call heapify recursively on the node $j$.

I suggest you try a few examples and see for yourself that sometimes the recursive call is necessary.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54543

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback