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

Stegman

The "binary tree" you showed is a min-heap, not a sorted binary tree. Was that your intention? – Pendant

@Pendant Hi! It just happens to be a min-heap. It wasn't intentional and can be any random complete or almost complete binary tree. – Stegman

"There are no arrays involved" - does this mean you are not allowed to copy the tree to an array and then heapify, or does this just mean you don't have the tree as an array originally? If the latter, copy to array, heapify, rebuild tree; that's O(n). – Thinner

@G.Bach Yes, you are not allowed to copy the tree to an array and then heapify and yes you don't have the tree as an array originally. Its a binary tree and not a binary tree visualization of the array. – Stegman

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

Aldarcie

Goto the left-most sub-tree?? So, do we need to use extra space for that to store addresses of non-leaf nodes through a level-order traversal? – Stegman

@ankitG No, just log(N) stack space to recurse on the left child and right child. Define a procedure "heapify" that first recursively calls itself on the left and right child of the current node, if there are any, then bubbles the current node down to its appropriate space. This is the same linear time algorithm you'd use on an array. – Baa

I think the complexity analysis here is off. If you think in terms of the tree's height H, you get O(H) = 2*O(H-1) + H, coming from (1) heapifying the two subtrees, and (2) bubbling the root down to its spot. This suggests that O(H) = 2^H, and thus O(N) = N. – Aylward

@SteveD is correct. If you implement this correctly, the complexity will be O(N) in time. You should be able to limit extra space (recursive stack depth) to O(log n). – Credence

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

Xenocrates

Thanks! Yeah! I too was doubtful about accessing the parent nodes in this situation but looks like we have to use extra space to store addresses of non-leaf nodes through a level-order traversal may be. – Stegman

But if we have to use an array(O(N)), why not store the binary tree in an array and then heapify it in O(n). My solution works in O(n^2) probably and doesn't use extra space. – Stegman

@ankitG heapify cost should be O(NlogN) in my memory, because you should check all node who has child node. – Xenocrates

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

}

Weighin

after you do the swap you need to check again if the subtree is still a heap – Amata

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

Codee