Max-Heapify A Binary Tree
I don't know the way if you can't access the parent node easily or no array representation, if you could traverse the tree to record it ref in a array(O(N)), then it become simple.
1
/ \
2 5
/ \ / \
3 4 6 7
from the last parent node to the root node(in your case 5,2,1:
for each node make it compare to their children:
if children is larger than parent, swap parent and children:
if swapped: then check the new children's childrens utill no swap
1
/ \
2 7
/ \ / \
3 4 6 5 check [7] 5<-->7
1
/ \
4 7
/ \ / \
3 2 6 5 check [2] 4<-->2
7
/ \
4 1
/ \ / \
3 2 6 5 check [1] 7<-->1
7
/ \
4 6
/ \ / \
3 2 1 5 check [1] 6<-->1
That is it! The complexity should be O(N*LogN).
I think this can be done in O(NlogN) time by the following procedure. http://www.cs.rit.edu/~rpj/courses/bic2/studios/studio1/studio121.html
Assume there is an element in the tree whose both left and right sub-trees are heaps.
E
H1 H2
This Tree formed by E, H1 and H2 can be heapified in logN time by making the element E swim down to its correct position.
Hence, we start building the heap bottom up. Goto the left-most sub-tree and convert it to a heap by trivial comparison. Do this for it's sibling as well. Then go up and convert it to heap.
Like-wise do this for every element.
EDIT: As mentioned in the comments, the complexity is actually O(N).