Heap Sort is a popular sorting algorithm that uses a binary heap data structure. It has a time complexity of O(n log n) in the average and worst cases. The algorithm consists of two main phases:

1. Building a max heap from the input data.
2. Repeatedly extracting the maximum element from the heap and rebuilding the heap until the array is sorted.

Java Implementation

public class HeapSort {
    // Main method to perform heap sort
    public void sort(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);
        }
    }

    // To maintain the heap property
    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);
        }
    }

    // Test the heap sort algorithm
    public static void main(String args[]) {
        HeapSort heapSort = new HeapSort();
        int arr[] = {12, 11, 13, 5, 6, 7};
        heapSort.sort(arr);

        System.out.println("Sorted array is:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Program Structure

The program is structured into the following main components:

• HeapSort Class: Contains the main logic for the heap sort algorithm.
• sort Method: Orchestrates the sorting process by first building the heap and then sorting the array.
• heapify Method: Ensures that the subtree with the root at index ‘i’ maintains the heap property.
• main Method: Entry point for the program that tests the heap sort functionality with an example array.

Documentation

Method Descriptions

• sort(int arr[]): Takes an integer array and sorts it in ascending order using heap sort.
• heapify(int arr[], int n, int i): Ensures the subtree rooted at index ‘i’ is a max heap. It takes the array, the size of the heap, and the index to be heapified as parameters.

Time Complexity

The time complexity of Heap Sort is O(n log n) for the average and worst cases. The space complexity is O(1) since it sorts the array in place.

Usage

To use this program, simply create an instance of the HeapSort class and call the sort method with an integer array as the argument.