1. Introduction

Heap Sort is a comparison-based sorting technique based on the Binary Heap data structure. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

2. Program Steps

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of the heap by one. Finally, heapify the root of the tree.

3. Repeat step 2 while the size of the heap is greater than 1.

3. Code Program

public class HeapSort {

    // Main function to do heap sort
    public static 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 heapify a subtree rooted with node i which is an index in arr[]
    static void heapify(int arr[], int n, int i) {
        int largest = i;  // Initialize largest as root
        int l = 2 * i + 1;  // left = 2*i + 1
        int r = 2 * i + 2;  // right = 2*i + 2

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

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

        // 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);
        }
    }

    // Driver method
    public static void main(String[] args) {
        int arr[] = {12, 11, 13, 5, 6, 7};

        // Call sort method to sort the array
        sort(arr);

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

Output:

Sorted array:
5 6 7 11 12 13

4. Step By Step Explanation

1. The heapify function is used to maintain the heap property. It ensures that the subtree rooted at a given index is a max-heap. If the heap property is violated, it recursively fixes the property by propagating the largest element up.

2. The primary logic of the heap sort resides in the sort function. It first builds a max-heap, ensuring that the largest element is at the root.

3. Once the max-heap is built, the root element (the largest element) is swapped with the last element in the array, reducing the heap size by 1. The root element is then heapified to maintain the max-heap property.

4. This process continues, extracting the maximum element from the heap and placing it at the end of the sorted section of the array until the entire array is sorted.

Heap Sort is an in-place sorting algorithm with a time complexity of O(n log n) for the worst, average, and best cases.