1
$\begingroup$

I tried watching http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and-heap-sort/ to understand heaps and heapsort but did not find this clear.

I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

$\endgroup$
  • $\begingroup$ Have you executed some example by hand? $\endgroup$ – Raphael Jan 28 '16 at 11:08
2
$\begingroup$

$Q_1:$ I do not understand the function of max-heapify. It seems like a recursive function, but then somehow it's said to run in logarithmic time because of the height of the tree.

max-heapify can be described as a recursive function. There is no particular prevention from a recursive function running in logarithmic time. For max-heapify, the recurrence is $T(n) \le T(2n/3) + \Theta(1)$ (here $2n/3$ is the worst case when the leaves is exactly half full; where $n$ is the size of the subtree rooted at the node under max-heapify). You can solve it by Master Theorem.

Another way of looking at max-heapify is to unfold the recursions: it "floats down" a value through a path of the subtree, whose length is $\sim \Theta(\lg n)$.

$Q_2:$ To me this makes no sense, because what if you run max-heapify on a min-heap? It'll have to reverse every single node, which I don't see how this can be done without it touching every single node.

The answer is simple: We don't run max-heapify on a min-heap. Use min-heapify for min-heap instead.

$\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.