Heapsort – MinHeap

/*Copyrights to vsdevelopers.io*/
/*For more programs visit vsdevelopers.io */
/*Java program for Heap sort using min Heap*/
public class VSDMinHeapSort {
	//Class to hold the structure of node in a tree
		public static class Node{
			int data;//Holds the value of node
			Node left;//Holds the left pointer of node
			Node right;//Holds the right pointer of node
			//Default constructor
			Node(int data)
		    {
		        this.data =data;
		        this.left = this.right = null;
		    }
		}
		//Root node
		public static Node root=null;
		//Variable to hold count of left nodes
		public static int leftcount=0;
		//Variable to hold count of right nodes
		public static int rightcount=0;
		//Variable to Maintain count of nodes in heap for appropriate deletion
		public static int deletecount=0;
		//Varaible to hold the appropriate child node for deletion
		public static Node deletenode=null;
		//Variable to hold the parent of child to be deleted
		public static Node parent=null;
		//Method to Build Heap along with maintanence of complete binary tree
	public static Node VSDbuildHeap(Node root,Node newNode)
	{
		if(root==null)root=newNode;//Null check
		else if(root.left!=null&&root.right!=null)//Checking whether both left and right children are present for the root
			{
				leftcount=VSDsubtreeCount(root.left);//Getting left nodes count from the left of current root
				rightcount=VSDsubtreeCount(root.right);//Getting right nodes count from the right of current root
				
				int height=VSDfindHeight(root);//Getting height of tree
				//Checking for the correct position to insert
				if(leftcount<(VSDexpectedCount(height)/2)) {
					VSDbuildHeap(root.left,newNode);
				}
				else if(leftcount==rightcount)
					VSDbuildHeap(root.left,newNode);
				else
					VSDbuildHeap(root.right,newNode);
			}
		else if(root.left==null)
			{
			root.left=newNode;
			
			}
		else if(root.right==null)
			{
			root.right=newNode;
			
			}
		
		
		return root;
	}
	//Function to maintain min heap properties
		public static Node VSDHeapify(Node current) {
			if(current.left!=null)
				current.left=VSDHeapify(current.left);
			if(current.right!=null)
				current.right=VSDHeapify(current.right);
			if(current.left!=null&&current.left.data<current.data)
			{
				int temp=current.left.data;
				current.left.data=current.data;
				current.data=temp;
			}
		 if(current.right!=null&&current.right.data<current.data) {
			int temp=current.right.data;
			current.right.data=current.data;
			current.data=temp;
		}
			return current;
		}
	//Function to return the expected node count for given height
	public static int VSDexpectedCount(int h) {
		int count=0;
		while(h>=0) {
			count+=Math.pow(2,h);
			h--;
		}
		return count;
	}
	//Function to return the node count for given subtree
	public static int VSDsubtreeCount(Node current) {
				int leftheight=0;//variable to hold height of left subtree
				int rightheight=0;//variable to hold height of right sub tree
				//Traversing to the left subtree to find min height
					if(current.left!=null)
						{
						leftheight=VSDsubtreeCount(current.left);
						}
					//Traversing to the right subtree to find min height
					if(current.right!=null) {
						rightheight=VSDsubtreeCount(current.right);
					}
					//selecting minimum height and adding 1 for root's height
					int count=rightheight+leftheight+1;
					 return count;
		}
	//Function to return the height of tree
	public static int VSDfindHeight(Node current) {
		if (current == null)
            return -1;
        else
        {
            int lh = VSDfindHeight(current.left);
            int rh = VSDfindHeight(current.right);
  
            if (lh > rh)
                return (lh + 1);
             else
                return (rh + 1);
        }
	}
//Function to display elements in min heap using inorder traversal
public static void VSDinorder(Node root) {
	if(root.left!=null)VSDinorder(root.left);
	 System.out.println(root.data);
	if(root.right!=null)VSDinorder(root.right);
	}
/*Function to choose the most recently inserted element based on count*/
public static void VSDchooseNode(Node current,int level,int size) {
	if(current==null) {
		return;
	}
	if(level==0) {
		deletecount++;
		if(deletecount==size/2) {
			parent=current;
		}
		if(deletecount==size) {
			deletenode=current;
			return;
		}
	}
	else if(level>0)
	{
		
		VSDchooseNode(current.left,level-1,size);
		VSDchooseNode(current.right,level-1,size);
	}
	
}
//Function to delete the root node from the heap
public static Node VSDdeleteNode(Node root,int height,int size) {
	//Obtain correct child node to replace with root
	for(int i=0;i<=height;i++) {
		VSDchooseNode(root,i,size);
	}
	int temp=root.data;
	root.data=deletenode.data;
	deletenode.data=temp;
	//Deleting the node
	if(parent.right!=null)parent.right=null;
	else parent.left=null;
	//calling heapify to maintain min heap properties
	root=VSDHeapify(root);
	return root;
}
public static void main(String args[]) {
	int[] arr=new int[]{10,11,13,6,25,17,12,5,4};
	Node n;
	for(int i=0;i<arr.length;i++) {
		n=new Node(arr[i]);
		root=VSDbuildHeap(root,n);
		root=VSDHeapify(root);//Calling function to maintain min heap properties
	}
	System.out.println("Insertion");
	VSDinorder(root);
	int size=arr.length;//Variable to hold the number of elements in heap
	System.out.println("The ascending order is:");
	while(size>1) {
		deletecount=0;
		System.out.println(root.data);
		int height=VSDfindHeight(root);
		root=VSDdeleteNode(root,height,size);
		size--;
	}
	System.out.println(root.data);
	root=null;
	
}
}