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