Max-Heapify A Binary Tree

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

}

Answer 4

Here's a working code for this problem.

package Test;


import static Test.BinaryTreeNode.swap;

public class TestImplementations {
    public static void main(String args[]){
        BinaryTreeNode root = new BinaryTreeNode(2,
                new BinaryTreeNode(7,
                        new BinaryTreeNode(5,
                                new BinaryTreeNode(1),new BinaryTreeNode(6)),
                        new BinaryTreeNode(9,
                                new BinaryTreeNode(17))),
                new BinaryTreeNode(3,
                        new BinaryTreeNode(11),new BinaryTreeNode(4))
                );
        System.out.println(root);
        CustomHeap h = new CustomHeap();
        h.minHeapify(root);
        System.out.println(root);
    }
}

class BinaryTreeNode {
    private  Integer value;
    private  BinaryTreeNode left;
    private  BinaryTreeNode right;

    public BinaryTreeNode(Integer value){
        this.value = value;
        this.left = null;
        this.right = null;
    }

    public BinaryTreeNode(Integer value, BinaryTreeNode left){
        this.value = value;
        this.left = left;
        this.right = null;
    }

    public BinaryTreeNode(Integer value, BinaryTreeNode left, BinaryTreeNode right){
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Integer getValue() {
        return value;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public static void swap(BinaryTreeNode r, BinaryTreeNode c){
        Integer val = r.getValue();
        r.value = c.getValue();
        c.value = val;
    }
}

class CustomHeap {
    public void minHeapify(Test.BinaryTreeNode r){
        if( r == null || (r.getLeft() == null && r.getRight() == null)){
            return;
        }
        minHeapify(r.getLeft());
        minHeapify(r.getRight());
        if(isMin(r,r.getLeft())){
            swap(r,r.getLeft());
            minHeapify(r.getLeft());
        }
        if(r.getRight() !=null && isMin(r,r.getRight())){
            swap(r,r.getRight());
            minHeapify(r.getRight());
        }
    }

    private Boolean isMin(Test.BinaryTreeNode r, Test.BinaryTreeNode c){
        return c.getValue() < r.getValue() ? Boolean.TRUE : Boolean.FALSE;
    }
}