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).