Heap Sort Algorithm

Heap Sort is a popular and efficient sorting algorithm in computer science. It falls under the category of comparison-based sorting algorithms. In this article, we will delve into the details of Heap Sort, how it works, its time and space complexity, and provide a step-by-step implementation in Java.

What is Heap Sort?

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to build a heap and perform the sorting. A heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, for any given node, the value of that node is greater than or equal to the values of its children. In a min-heap, the value of the node is less than or equal to its children.

The algorithm works by first building a heap from the input array, where the largest (for max-heap) or smallest (for min-heap) element is at the root. It then swaps the root element with the last element of the heap (representing the maximum or minimum element), effectively "removing" it from the heap. After each removal, the heap property is restored by heapifying the remaining elements. This process is repeated until the heap is empty, resulting in a sorted array.

How does Heap Sort work?

The Heap Sort algorithm can be divided into two main phases: building the heap and extracting elements.

1. Building the Heap

• Max Heap (for ascending order): Start by building a max heap from the given input array. This ensures that the maximum element is at the root of the heap.
• Min Heap (for descending order): Build a min heap to have the minimum element at the root.

2. Extracting Elements

• Swap the root element (maximum or minimum) with the last element in the heap and reduce the heap size by one.
• Restore the heap property by heapifying the new root.
• Repeat the swapping and heapifying steps until the heap is empty.

The resulting array will be sorted either in ascending or descending order, depending on whether a max heap or a min heap was used.

Java Code

import java.util.Arrays;

public class HeapSort {

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

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

       // One by one extract an element from heap
       for (int i = n - 1; i >= 0; i--) {
           // Move current root to end
           int temp = arr[0];
           arr[0] = arr[i];
           arr[i] = temp;

           // call max heapify on the reduced heap
           heapify(arr, i, 0);
       }
   }

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

       // If left child is larger than root
       if (left < n && arr[left] > arr[largest])
           largest = left;

       // If right child is larger than largest so far
       if (right < n && arr[right] > arr[largest])
           largest = right;

       // If largest is not root
       if (largest != i) {
           int swap = arr[i];
           arr[i] = arr[largest];
           arr[largest] = swap;

           // Recursively heapify the affected sub-tree
           heapify(arr, n, largest);
       }
   }

   public static void main(String[] args) {
       int[] arr = {12, 11, 13, 5, 6, 7};
       System.out.println("Original array: " + Arrays.toString(arr));

       heapSort(arr);

       System.out.println("Sorted array: " + Arrays.toString(arr));
   }
}

Output

Original array: [12, 11, 13, 5, 6, 7]
Sorted array: [5, 6, 7, 11, 12, 13]

Time and Space Complexity

Heap Sort is known for its efficiency and has a time complexity of O(n log n) in all cases, making it asymptotically optimal. This is because both the building phase and the extraction phase have a time complexity of O(n log n). However, it is not a stable sorting algorithm.

The space complexity of Heap Sort is O(1) as it sorts the array in-place without requiring additional space proportional to the input size.

Summary

Heap Sort is a highly efficient sorting algorithm with a time complexity of O(n log n) and a space complexity of O(1). Understanding how Heap Sort works and its implementation in Java is valuable knowledge for any programmer. Utilize this sorting algorithm when you need a fast and in-place sorting solution.