Heap Sort in Java

Heap sort is a comparison-based sorting technique which is based on Binary Heap Data Structure. Heap Sort is an optimization of selection sort where we first find the max (or min) element swapping it with the last (or first). and we repeat the same process for the remaining elements. In Heap Sort, we use Binary Heap which quickly find and move the max element in O(Log n) instead of O(n) and hence it has time complexity O(n Log n).

Heap Sort Algorithm

Step 1 : First convert the array into a max heap using heapify and The array elements are re-arranged to follow heap properties.

Step 2 : Then one by one delete the root node of the Max-heap and replace it with the last node and heapify.

Step 3 : Repeat this process while size of heap is greater than 1.

Step 4 : Rearrange array elements so that they form a Max Heap.

Step 5 : Repeat the following steps until the heap contains only one element:

a) Swap the root element of the heap, which is the largest element in current heap, with the last element of the heap.

b) Remove the last element of the heap which is now in the correct position.

c) Heapify the remaining elements of the heap.

Step 6 : Finally we get sorted array.

Heap Sort Algorithm Syntax

HeapSort(array)
    n = length(array)
    for i from n/2 - 1 to 0 do
        heapify(array, n, i)
    for i from n-1 to 0 do
        swap(array[0], array[i])
        heapify(array, i, 0)
heapify(array, n, i)
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and array[left] > array[largest] then
        largest = left
    if right < n and array[right] > array[largest] then
        largest = right
    if largest != i then
        swap(array[i], array[largest])
        heapify(array, n, largest)

Heap Sort Complexity :

Time Complexity :

Best Case : O(n logn)

When there is no sorting required, which is when the array is already sorted, the best-case time complexity of heap sort is O(n logn).

Average Case : O(n log n)

When the array elements are in jumbled order that is neither ascending nor descending, the average case time complexity of heap sort is O(n log n).

Worst Case : O(n log n)

When the array elements are required to be sorted in reverse order,the worst case time complexity of heap sort is O(n log n).

Space Complexity :

Space Complexity : O(1)

Stable : No

Advantages of Heap Sort :

1) Heap Sort has a time complexity of O(n log n) in all cases which makes it efficient for sorting large datasets.
2) Memory usage can be minimal by writing an iterative heapify() instead of a recursive one and it needs no additional memory space to work.
3) It is simpler to understand than other equally efficient sorting algorithms.

Disadvantages of Heap Sort :

1) Heap sort is costly as the constants are higher compared to merge sort even if the time complexity is O(n Log n) for both.
2) Heap sort is unstable and might rearrange the relative order
3) Heap Sort is not very efficient because of the high constants in the time complexity.

Heap Sort Applications :

1) Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort’s running time and constant O(1) upper bound on its auxiliary storage.
2) Heap Sort’s data structure, heap, can be efficiently used if we want to extract the smallest (or largest) from the list of items without the overhead of keeping the remaining items in the sorted order. For e.g Priority Queues.

Program : Heap Sort in Java

public class HeapSortProg {

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

        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

    public void heapify(int arr[], int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }
  
    public static void main(String args[]) {
	  
	  int[] arr = {14, 6, 23, 42, 19, 37};
	  
	  System.out.println("Unsorted Array");
			for (int val : arr) {
	            System.out.print(val + " ");  
	        }

  
	  HeapSortProg hs_obj = new HeapSortProg();
      hs_obj.heapSortFunction(arr);
  
      System.out.println("\n\n" + "Sorted Array in Ascending Order: ");
	        for (int val : arr) {
	            System.out.print(val + " ");  
	        }
    }    
}
Output :

Unsorted Array
14 6 23 42 19 37 

Sorted Array in Ascending Order: 
6 14 19 23 37 42

Related Posts

Scroll to Top