Heap Sort

Heap Sort Algorithm: Sorting in ascending order
Max Heap: when the value of root node element is grater than or equal to left and right, called Max Heap.

Min Heap: When the value of root node element is less than or equal to left and right, called Min Heap.

• We can use Heap Sort with very large amount of data.
• Time Complexity: O(nLogn)
• Space Complexity : O(1).

package dataStructure;

public class HeapSort {

 public static void main(String[] args) {
  int[] arr = { 14, 11, 17, 5, 6, 9 };
  System.out.print("Input: array is: ");
  printArray(arr);

  HeapSort ob = new HeapSort();
  ob.heapSort(arr);

  System.out.print("Output: Sorted array is: ");
  printArray(arr);
 }

 public void heapSort(int[] arr) {
  int n = arr.length;

  // build a map heap (by rearrange array elements)
  for (int i = n / 2 - 1; i >= 0; i--) {
   heapify(arr, n, i);
  }

  // One by one extract an Max element from heap
  for (int i = n - 1; i > 0; i--) {
   // Move current root to end of array
   int temp = arr[0];
   arr[0] = arr[i];
   arr[i] = temp;

   // call max heapify on the reduced heap
   heapify(arr, i, 0);
  }
 }

 /**
  * To heapify a subtree with node i which is an index in dataArr[]
  * 
  * @param dataArr
  * @param n       is size of heap
  * @param i       is the root element index
  */
 void heapify(int[] dataArr, int n, int i) {
  // Find largest among root, left child and right child
  int root = i; // Initialize largest element as root
  int left = 2 * i + 1; // left element index
  int right = 2 * i + 2; // right element index

  // check If left child is larger than root then assign left element as root
  if (left < n && dataArr[left] > dataArr[root]) {
   root = left;
  }

  // check If right child is larger than root then assign right element as root
  if (right < n && dataArr[right] > dataArr[root]) {
   root = right;
  }

  // If root element is not larger than left or right element then swap element
  if (root != i) {
   int swap = dataArr[i];
   dataArr[i] = dataArr[root];
   dataArr[root] = swap;

   // Recursively heapify the affected sub-tree
   heapify(dataArr, n, root);
  }
 }

 /* A utility function to print array of size n */
 static void printArray(int[] arr) {
  int n = arr.length;
  for (int i = 0; i < n; ++i)
   System.out.print(arr[i] + " ");
  System.out.println();
 }

}

Output:

Input: array is: 14 11 17 5 6 9 
Output: Sorted array is: 5 6 9 11 14 17 

Heap Sort Algorithm: Sorting in descending order - we have to create min Heap for this.