Heap Sort in Java

Posted on Updated on

Heap Sort is a comparison-based sorting algorithm to create a sorted array. It is similar to selection sort where we first find the maximum element from array and place it at the end. We repeat this process for each element in the given array. Heap Sort is based on Binary Heap data structure. In this program we will be sorting the given array in ascending order.

Time Complexity of Heap Sort

  • Worst case performance : O(n log n)
  • Best case performance : O(n log n)
  • Average case performance : O(n log n)

Algorithm to sort array in ascending order.

  • Build Max Heap from given array.
  • Now the root of heap will contain max element, replace it with last element of heap followed by reducing the size of heap by 1 and apply heapify process.
  • Repeat above steps for each element of the given array.

Java program to sort an array using Heap Sort Algorithm in ascending order.

Output

Note: Above program sorts an array in ascending order. In case you have to sort an array in descending order, you need to create Min Heap instead of Max Heap and your heapify method should be like

Output after replacing heapify method to MinHeap

 

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.