Heap sort in java


Contents of page >
  • Full Program/SourceCode/Example to sort array using heap sort in java>
  • Output of heap sort program >


Also read : Radix sort



Full Program/SourceCode/Example to sort array using heap sort in java>
/**
*  write a program to sort array using Heap Sort in java.
*/
public class HeapSortAlgorithmExample {
   /**
   * Declare initialize array which has to be sorted using Heap sort in java
   */
   private int[] arr = { 12, 3, 8, 9, 1, 14, 6, 7, 5, 89 };
   /**
   * This method Sort Array using Heap Sort in java
   */
  
   public void heapSort(){
       int n = arr.length;
       // First we need to build the heap or rearrange array,
       // so call heapify method
       for (int i = n / 2 - 1; i >= 0; i--)
        heapify( n, i);
       //Get all the elements from heap
          for (int i = n - 1; i >= 0; i--) {
                
                 // Shift the root to end
                 int temp = arr[0];
                 arr[0] = arr[i];
                 arr[i] = temp;
                 //Again call the heapify method,
                 //This time heap must be reduced
                 //So, this time call the reduced heap heapify with largest number
                 heapify(i, 0);
          }
   }
   // n is size of heap
   // Method to heapify
   void heapify(int n, int i) {
         
          //As of now root is the largest
          int largest = i;
         
          int left = 2 * i + 1;
          int right = 2 * i + 2;
          // If left node is larger than root
          // Than assign left node to larger
          if (left < n && arr[left] > arr[largest])
                 largest = left;
          // If right node is larger than largest
          // Than assign right node to larger
          if (right < n && arr[right] > arr[largest])
                 largest = right;
          // If largest is not root
          if (largest != i) {
                 //do swapping
                 swap(arr[i], i, largest);
                
                 // Now, recursively call heapify method to heapify the sub tree
                 heapify(n, largest);
          }
   }
  
   void swap(int swap, int i, int largest){
          arr[i] = arr[largest];
          arr[largest] = swap;
   }
   /**
   * This method Display Array
   */
   public void display() {
          for (int i = 0; i < arr.length; i++) {
                 System.out.print(arr[i] + " ");
          }
   }
   public static void main(String[] args) {
          HeapSortAlgorithmExample heapSort = new HeapSortAlgorithmExample();
          System.out.print("Display Array elements before Heap sorting : ");
          heapSort.display(); // display unsorted array
          heapSort.heapSort(); // heap sort the array
          System.out.print("\nDisplay Array elements after Heap sorting  : ");
          heapSort.display(); // display sorted array
   }
}
/*output
Display Array elements before Heap sorting : 12 3 8 9 1 14 6 7 5
Display Array elements after Heap sorting  : 1 3 5 6 7 8 9 12 14
*/

Output of heap sort program >
Display Array elements before Heap sorting : 12 3 8 9 1 14 6 7 5
Display Array elements after Heap sorting  : 1 3 5 6 7 8 9 12 14

Summary >
So in this data structure tutorial we learned Heap sort in java.

Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.




eEdit
Must read for you :