# 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

I was looking for a better solution. Can somebody please help?

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; }

## Answers

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; } }