## Saturday, August 29, 2020

### 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;
arr = 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.