1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible. Please take some time to improve your post in this regard. We have collected some advice here. $\endgroup$
    – Raphael ♦
    Mar 16, 2016 at 15:13
  • 1
    $\begingroup$ These lines can only be understood in the context of the rest. It does not make much sense to ask about one line in isolation. $\endgroup$
    – Raphael ♦
    Mar 16, 2016 at 15:14
  • 2
    $\begingroup$ Part of our mission on this site is to build up a repository of high-quality questions and answers that might be useful to others in the future. $\endgroup$
    – D.W. ♦
    Mar 16, 2016 at 17:31
  • $\begingroup$ Plus, for all we know Yuval has another variant of the algorithm and his answer doesn't fit yours at all, but you are not in the position to notice. (I'd hope that he clicked through to that PDF, but it's generally better not to assume that.) $\endgroup$
    – Raphael ♦
    Mar 17, 2016 at 8:06

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\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.