Heap Sort Using Java

Code :

//program for heap sort
import java.util.*;

public class Heap
{
static void adjust(int a[],int i,int n)
{
int j,x;

j = i*2;
x = a[i];

while(j <= n)
{
if(j < n && a[j] < a[j+1])
j = j+1;
if(x > a[j])
break;

a[j/2] = a[j];

j = j*2;
}

a[j/2] = x;
}//end adjust

public static void main(String args[])
{
System.out.println("Enter number of elements you wish to sort : ");
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

//declare array of n+1 elements

int a[] = new int[n+1];
//scan array from 1 to n locations
for(int i = 1; i <= n;i++)
{
System.out.print("\nEnter element " + i + " : ");
a[i] = sc.nextInt();
}

System.out.println("\nOriginal array : ");

for(int i=1;i<=n;i++)
System.out.print(a[i] + " ");

//construct heap

for(int i = n/2 ; i >= 1; i--)
adjust(a,i,n);

//heap sort

int t;

for(int i = n;i >= 2;i--)
{
t = a[1];
a[1] = a[i];
a[i] = t;

adjust(a,1,i-1); //reheapify
}

//print sorted array

System.out.println("\nSorted array : ");

for(int i=1;i<=n;i++)
System.out.print(a[i] + " ");
}

}


Output :


Enter number of elements you wish to sort :
5

Enter element 1 : 5

Enter element 2 : 4

Enter element 3 : 1

Enter element 4 : 2

Enter element 5 : 6

Original array :
5 4 1 2 6
Sorted array :
1 2 4 5 6