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&¤t.left.data<current.data)
{
int temp=current.left.data;
current.left.data=current.data;
current.data=temp;
}
if(current.right!=null&¤t.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;
}
}