Code:
import java.util.Scanner;
/* Class HeapSort */
public class HeapSort
{
private static int N;
/* Sort Function */
public static void sort(int arr[])
{
heapify(arr);
for (int i = N; i > 0; i--)
{
swap(arr,0, i);
N = N-1;
maxheap(arr, 0);
}
}
/* Function to build a heap */
public static void heapify(int arr[])
{
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
/* Function to swap largest element in heap */
public static void maxheap(int arr[], int i)
{
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i)
{
swap(arr, i, max);
maxheap(arr, max);
}
}
/* Function to swap two numbers in an array */
public static void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/* Main method */
public static void main(String[] args)
{
Scanner scan = new Scanner( System.in );
System.out.println("Heap Sort Test\n");
int n, i;
/* Accept number of elements */
System.out.println("Enter number of integer elements");
n = scan.nextInt();
/* Make array of n elements */
int arr[] = new int[ n ];
/* Accept elements */
System.out.println("\nEnter "+ n +" integer elements");
for (i = 0; i < n; i++)
arr[i] = scan.nextInt();
/* Call method sort */
sort(arr);
/* Print sorted Array */
System.out.println("\nElements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
Output:
Enter number of integer elements
20
Enter 20 integer elements
488 667 634 380 944 594 783 584 550 665 721 819 285 344 503 807 491 623 845 300
Elements after sorting
285 300 344 380 488 491 503 550 584 594 623 634 665 667 721 783 807 819 845 944
Heap Sort Test
Enter number of integer elements
20
Enter 20 integer elements
57 205 342 200 197 946 631 92 66 581 345 220 398 249 329 87 186 144 462 431
Elements after sorting
57 66 87 92 144 186 197 200 205 220 249 329 342 345 398 431 462 581 631 946
Heap Sort Test
Enter number of integer elements
20
Enter 20 integer elements
802 327 219 415 648 783 250 891 232 822 604 123 138 505 883 224 86 681 51 310
Elements after sorting
51 86 123 138 219 224 232 250 310 327 415 505 604 648 681 783 802 822 883 891
More Java Programs:
