**What is Heap Sort??**

- Heap sort is comparison based sorting algorithm.
- Heap sort is considered as improved selection sort, it divides the input into sorted and unsorted region.
- The improvement from selection sort is to use Heap Data Structure instead of using linear search algorithm to reduce of the time complexity.

**Pre-requisite:**

Binary Heap (min and max heap)

**What is Binary Heap??**

Heap is a tree based data structure which satisfies the two properties

**Shape Property**: Heap data structure is always a Complete Binary Tree. The Complete Binary tree is a binary tree which is completely filled (means all the nodes has 2 children) except the last level which might not be completely full.

Heap Property: All nodes are either greater than equal to (* Max-Heap*) or less than equal to (

*) to each of its child nodes. This is called*

**Min-Heap***.*

**heap property**** How Heap Sort Algorithm works???**

- Sorting in ascending order:
- Create a max Heap from the given input array.
- Extract the root (it will be the maximum value in array) and replace it with the last element in the array.
- Heapify the root of the heap.
- Repeat the steps b and c till entire array is sorted.

- Sorting in descending order
- Create a min Heap from the given input array.
- Extract the root (it will be the minimum value in array) and replace it with the last element in the array.
- Heapify the root of the heap.
- Repeat the steps b and c till entire array is sorted.

**Time Complexity**: O(nLogn)

**See the video below for more understanding**

**Complete Java Code for Heap Sort**:

import java.util.Arrays; | |

public class HeapSort { | |

public void sort(int arrA[]) { | |

int size = arrA.length; | |

// Build heap | |

for (int i = size / 2 – 1; i >= 0; i—) | |

heapify(arrA, size, i); | |

// One by one extract (Max) an element from heap and | |

// replace it with the last element in the array | |

for (int i=size–1; i>=0; i—) { | |

//arrA[0] is a root of the heap and is the max element in heap | |

int x = arrA[0]; | |

arrA[0] = arrA[i]; | |

arrA[i] = x; | |

// call max heapify on the reduced heap | |

heapify(arrA, i, 0); | |

} | |

} | |

// To heapify a subtree with node i | |

void heapify(int arrA[], int heapSize, int i) { | |

int largest = i; // Initialize largest as root | |

int leftChildIdx = 2*i + 1; // left = 2*i + 1 | |

int rightChildIdx = 2*i + 2; // right = 2*i + 2 | |

// If left child is larger than root | |

if (leftChildIdx < heapSize && arrA[leftChildIdx ] > arrA[largest]) | |

largest = leftChildIdx ; | |

// If right child is larger than largest so far | |

if (rightChildIdx < heapSize && arrA[rightChildIdx ] > arrA[largest]) | |

largest = rightChildIdx ; | |

// If largest is not root | |

if (largest != i) { | |

int swap = arrA[i]; | |

arrA[i] = arrA[largest]; | |

arrA[largest] = swap; | |

// Recursive call to heapify the sub-tree | |

heapify(arrA, heapSize, largest); | |

} | |

} | |

public static void main(String args[]) { | |

int arrA[] = {9, 10, 5, 3, 1, 2, 6}; | |

System.out.println("Original array is: " + Arrays.toString(arrA)); | |

HeapSort heapSort = new HeapSort(); | |

heapSort.sort(arrA); | |

System.out.println("Sorted array is (Heap Sort): " + Arrays.toString(arrA)); | |

} | |

} |

**Output**:

Original array is: [9, 10, 5, 3, 1, 2, 6] Sorted array is (Heap Sort): [1, 2, 3, 5, 6, 9, 10]