Recursive Heapify

[philmetz]

Hey

I am a bit confused on how the Recursive heapify process works.
So tell me If I have this right:
It first goes to the left subtree until it reaches the last Node, it then starts the tickleup process and continues like that.
It then goes to right subtree and does the same

Here is some code:

heapify(int index) // transform array into heap
{
       if(index > N/2-1) // if node has no children,
                return; // return
       heapify(index*2+2); // turn right subtree into heap
       heapify(index*2+1); // turn left subtree into heap
       trickleDown(index); // apply trickle-down to this node
}

Thanks

[shrughes]

What trickleup process are you talking about?

heapify builds the two child heaps and then trickles the root node into one of them.

Your real problem is that you aren't thinking recursively.

[philmetz]

Trickle up i was thinking take a node and compare with parent and swap if needed

What do you mean builds?

[shrughes]

By "builds" I'm only saying that permutes some elements of your array into the appropriate locations such that they form a heap.

But whatever. You should avoid thinking of the recursive process as "going to the last node and then blah blah blah." People who think poorly about recursion end up trying to visualize the process that way, and it fails them. It is fine and dandy to simulate the process with various examples, but to understand why it works, you need to think recursively. That means reasoning based on an assumption about the net effects of your function's recursive calls.

So the question is that of why heapify works. Well, we call heapify on two subtrees (that happen to be encoded in an array, but that's not the hard part). Assuming that heapify works properly on smaller trees, we now have two heaps. And then trickledown successfully combines an element and two heaps into a single heap.

[philmetz]

hmm i see
By "thinking recursively" do you have any tips how to do that properly?

[Rashakil Fol]

I don't know what makes you think there's a "proper" way to think recursively.

But as the other poster said, thinking recursively means reasoning based on an assumption about the net effects of your function's recursive calls. And an example was given too.