# Max-Heapify A Binary Tree

This is one of the interview questions I recently came across.

Given the root address of a complete or almost complete binary tree, we have to write a function to convert the tree to a max-heap.

There are no arrays involved here. The tree is already constructed.

For e.g.,

```              1
/         \
2           5
/   \       /   \
3      4    6     7
```

can have any of the possible max heaps as the output--

```              7
/         \
3           6
/   \       /   \
2     1     4     5
```

or

```              7
/         \
4           6
/   \       /   \
2     3     1     5
```

etc...

I wrote a solution but using a combination of pre and post order traversals but that I guess runs in O(n^2). My code gives the following output.

```              7
/         \
3           6
/   \       /   \
1     2     4     5
```

Edit :

##### My Code
```void preorder(struct node* root)
{
if(root==NULL)return;
max_heapify(root,NULL);
preorder(root->left);
preorder(root->right);
}
void max_heapify(struct node* root,struct node* prev)
{
if(root==NULL)
return ;
max_heapify(root->left,root);
max_heapify(root->right,root);
if(prev!=NULL && root->data > prev->data)
{
swapper(root,prev);
}
}
void swapper(struct node* node1, struct node* node2)
{
int temp= node1->data;
node1->data = node2->data;
node2->data = temp;
}
```

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

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 you can get one work simply by revising postOrderTraverse. This is O(n)

```void Heapify_Min(TreeNode* node)
{
if(! = node) return;
Heapify_Min(node->left);
Heapify_Min(node->right);
TreeNode* largest = node;
if(node->left && node->left->val > node->val)
largest = node->left;
if(node->right && node->right->val > node->val)
largest = node->right;

if(largest != node)
{
swap(node, largest)
}
}

void swap(TreeNode* n1, TreeNode* n2)
{
TreeNode* temp = n1->left;
n1->left = n2->left;
n2->left =temp;

temp = n1->right;
n1->right = n2->right;
n2->right = temp;
}

}
```