
import java.util.*;
public class HeapSort {
    private int x[],n,m;
    public HeapSort(int n)
    {
        this.n=n;
        x=new int[n];
        System.out.println("Enter"+n+"Elements");
        Scanner src=new Scanner(System.in);
        for(int i=0;i<n;i++)
            x[i]=src.nextInt();
    }
    public void heapUp(int root,int bottom)
    {
        int parent,temp;
        if(bottom>root)
        {
            parent=(bottom-1)/2;
            if(x[parent]<x[bottom])
            {
                temp=x[parent];
                x[parent]=x[bottom];
                x[bottom]=temp;
                heapUp(root,parent);
            }
        }
    }
    public void heapDown(int root,int bottom)
    {
        int lchild,rchild,mchild,temp;
        lchild=2*root+1;
        rchild=2*root+2;
        if(lchild<=bottom)
        {
            if(lchild==bottom)
                  mchild=lchild;
            else if(x[lchild]>x[rchild])
                mchild=lchild;
            else mchild=rchild;
            if(x[root]<x[mchild])
            {
                temp=x[root];
                x[root]=x[mchild];
                x[mchild]=temp;
                heapDown(mchild,bottom);
        }
    }

}
    public void heapSort()
    {
        int i,temp;
        for(i=0;i<n-1;i++)
            heapUp(0,i+1);
        System.out.println("After initial max heap");
        display();
        for(i=n-1;i>=1;i--)
        {
            temp=x[0];
            x[0]=x[i];
            x[i]=temp;
            System.out.println("After heap down");
            heapDown(0,i-1);
            display();
        }
    }
    public void display()
    {
        for(int i=0;i<n;i++)
            System.out.print(x[i]+" ");
        System.out.println();
    }
}
class HeapExp
{
    public static void main(String args[])
    {
        Scanner src=new Scanner(System.in);
        System.out.println("\nEnter number of elements");
        int n=src.nextInt();
        HeapSort obj=new HeapSort(n);
        obj.heapSort();
        System.out.println("\nSorted Array");
        obj.display();
    }
}

O/P:

Enter number of elements
5
Enter5Elements
23
12
5
49
78
After initial max heap
78 49 5 12 23 
After heap down
49 23 5 12 78 
After heap down
23 12 5 49 78 
After heap down
12 5 23 49 78 
After heap down
5 12 23 49 78 

Sorted Array
5 12 23 49 78 
BUILD SUCCESSFUL (total time: 11 seconds)
