Java Program to Sort 10 Elements using Heap Sort Algorithm

This is a java program to perform Heap Sort. There are two types of heaps. First one is Max heap and second one is Min heap. Heap (Max/Min) is a special type of binary tree.The roots of the max heap is greater than its child roots. Other heap is Min heap it is also a special type of heap which has minimum root than his child. We can sort the array values using heap sorting algorithm. In this algorithm the heap build is used to rebuild the heap. In this example we sorting all elements of an array. The complexity of the heap sort is O(n.log(n)) since the method build heap takes time O(n) and each of the (n-1) calls to maxheap takes time O(lg n).

Here is the source code of the Java Program to Sort an Array of 10 Elements Using Heap Sort Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to perform sorting of randomly generated using Heap Sort
  2. import java.util.Random;
  3.  
  4. public class Heapsort
  5. {
  6.     private static int[] a;
  7.     private static int   n;
  8.     private static int   left;
  9.     private static int   right;
  10.     private static int   largest;
  11.  
  12.     public static void buildheap(int[] a)
  13.     {
  14.         n = a.length - 1;
  15.         for (int i = n / 2; i >= 0; i--)
  16.         {
  17.             maxheap(a, i);
  18.         }
  19.     }
  20.  
  21.     public static void maxheap(int[] a, int i)
  22.     {
  23.         left = 2 * i;
  24.         right = 2 * i + 1;
  25.         if (left <= n && a[left] > a[i])
  26.         {
  27.             largest = left;
  28.         } else
  29.         {
  30.             largest = i;
  31.         }
  32.  
  33.         if (right <= n && a[right] > a[largest])
  34.         {
  35.             largest = right;
  36.         }
  37.         if (largest != i)
  38.         {
  39.             exchange(i, largest);
  40.             maxheap(a, largest);
  41.         }
  42.     }
  43.  
  44.     public static void exchange(int i, int j)
  45.     {
  46.         int t = a[i];
  47.         a[i] = a[j];
  48.         a[j] = t;
  49.     }
  50.  
  51.     public static void sort(int[] a0)
  52.     {
  53.         a = a0;
  54.         buildheap(a);
  55.  
  56.         for (int i = n; i > 0; i--)
  57.         {
  58.             exchange(0, i);
  59.             n = n - 1;
  60.             maxheap(a, 0);
  61.         }
  62.     }
  63.  
  64.     public static void main(String[] args)
  65.     {
  66.         int N = 20;
  67.         int[] sequence = new int[N];
  68.         Random random = new Random();
  69.  
  70.         System.out.println("Heap Sort Test");
  71.  
  72.         for (int i = 0; i < N; i++)
  73.             sequence[i] = Math.abs(random.nextInt(100));
  74.  
  75.         System.out.println("The original sequence is: ");
  76.         for (int i = 0; i < sequence.length; i++)
  77.             System.out.print(sequence[i] + " ");
  78.  
  79.         sort(sequence);
  80.  
  81.         System.out.println("\nThe sorted sequence is: ");
  82.         for (int i = 0; i < sequence.length; i++)
  83.             System.out.print(sequence[i] + " ");
  84.     }
  85. }

Output:

$ javac Heapsort.java
$ java Heapsort
 
Heap Sort Test
The original sequence is: 
3 72 19 49 3 20 91 47 6 25 71 94 15 81 86 66 29 20 21 82 
The sorted sequence is: 
3 3 6 15 19 20 20 21 25 29 47 49 66 71 72 81 82 86 91 94

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.