Program:
import java.io.*;
class arraylist
{
private int[] a;
private int n;
private int[] temp;
public arraylist(int x)
{
a = new int[x];
n=0;
temp = new int[x];
}
public void insert(int e)
{
n++;
a[n]=e;
}
public void display()
{
for(int i=1;i<=n;i++)
System.out.print(a[i]+" ");
System.out.println("\n");
}
public void swap(int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
}
public void buildheap()
{
for(int i=n/2;i>=1;i--)
maxheapify(n,i);
}
public void maxheapify(int n,int i)
{
int largest;
int l=left(i);
int r=right(i);
if(l<=n&&a[l]>a[i])
largest=l;
else
largest=i;
if(r<=n&&a[r]>a[largest])
largest=r;
if(largest!=i)
{
swap(i,largest);
maxheapify(n,largest);
}
}
public void heapsort()
{
buildheap();
int heapsize=n;
for(int i=heapsize;i>=2;i--)
{
swap(i,1);
display();
heapsize--;
maxheapify(heapsize,1);
}
}
public int left(int a)
{
return 2*a;
}
public int right(int b)
{
return 2*b+1;
}
}
class heapsort
{
public static void main(String arg[]) throws IOException
{
DataInputStream x1= new DataInputStream(System.in);
System.out.print("\nEnter the number of elements:");
int na=Integer.parseInt(x1.readLine());
arraylist ob=new arraylist(na+1);
System.out.println("Enter the elements:");
for (int k=1;k<=na;k++)
ob.insert(Integer.parseInt(x1.readLine()));
System.out.println("Before sorting:\n");
ob.display();
System.out.println("Sorting.............");
System.out.print("(HeapSort)\n\n");
ob.display();ob.heapsort();
System.out.println("After sorting:\n");
ob.display();
}
}
Output:
nn@linuxmint ~ $ javac heapsort.java
Note: heapsort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java heapsort
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
Before sorting:
5 4 3 2 1
Sorting.............
(HeapSort)
5 4 3 2 1
1 4 3 2 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
After sorting:
1 2 3 4 5
nn@linuxmint ~ $
import java.io.*;
class arraylist
{
private int[] a;
private int n;
private int[] temp;
public arraylist(int x)
{
a = new int[x];
n=0;
temp = new int[x];
}
public void insert(int e)
{
n++;
a[n]=e;
}
public void display()
{
for(int i=1;i<=n;i++)
System.out.print(a[i]+" ");
System.out.println("\n");
}
public void swap(int x,int y)
{
int temp=a[x];
a[x]=a[y];
a[y]=temp;
}
public void buildheap()
{
for(int i=n/2;i>=1;i--)
maxheapify(n,i);
}
public void maxheapify(int n,int i)
{
int largest;
int l=left(i);
int r=right(i);
if(l<=n&&a[l]>a[i])
largest=l;
else
largest=i;
if(r<=n&&a[r]>a[largest])
largest=r;
if(largest!=i)
{
swap(i,largest);
maxheapify(n,largest);
}
}
public void heapsort()
{
buildheap();
int heapsize=n;
for(int i=heapsize;i>=2;i--)
{
swap(i,1);
display();
heapsize--;
maxheapify(heapsize,1);
}
}
public int left(int a)
{
return 2*a;
}
public int right(int b)
{
return 2*b+1;
}
}
class heapsort
{
public static void main(String arg[]) throws IOException
{
DataInputStream x1= new DataInputStream(System.in);
System.out.print("\nEnter the number of elements:");
int na=Integer.parseInt(x1.readLine());
arraylist ob=new arraylist(na+1);
System.out.println("Enter the elements:");
for (int k=1;k<=na;k++)
ob.insert(Integer.parseInt(x1.readLine()));
System.out.println("Before sorting:\n");
ob.display();
System.out.println("Sorting.............");
System.out.print("(HeapSort)\n\n");
ob.display();ob.heapsort();
System.out.println("After sorting:\n");
ob.display();
}
}
Output:
nn@linuxmint ~ $ javac heapsort.java
Note: heapsort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
nn@linuxmint ~ $ java heapsort
Enter the number of elements:5
Enter the elements:
5
4
3
2
1
Before sorting:
5 4 3 2 1
Sorting.............
(HeapSort)
5 4 3 2 1
1 4 3 2 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
After sorting:
1 2 3 4 5
nn@linuxmint ~ $
Checkout other sorting programs here.....
ReplyDeleteHeap Sort in C
Bubble Sort in C
Insertion Sort in C
Selection Sort in C
Quick Sort in C