**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**:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

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]