Heap Sort Algorithm in Java

1. Introduction

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It divides the input into a sorted and an unsorted region and iteratively shrinks the unsorted region by extracting the largest element and moving it to the sorted region.

2. Implementation Steps

1. Build a max heap from the input data.

2. The largest item is stored at the root of the max heap. Replace it with the last item of the heap, followed by reducing the size of the heap by 1.

3. Finally, heapify the root of the tree.

4. Repeat the above steps while the size of the heap is not one.

3. Implementation in Java

public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;
        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i);
        }
        // Extract elements from heap one by one
        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);
        }
    }
    void heapify(int arr[], int n, int i) {
        int largest = i;  // Initialize largest as root
        int l = 2 * i + 1;  // Left child
        int r = 2 * i + 2;  // Right child
        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;
        // If right child is larger than 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);
        }
    }
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        int n = arr.length;
        HeapSort ob = new HeapSort();
        ob.sort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

Output:

Sorted array:
5 6 7 11 12 13

Explanation:

1. Start by transforming the list into a max heap. A max heap is a specialized tree-based data structure that satisfies the property that the parent node's key is greater than the keys of its children.

2. Once the list has been transformed into a max heap, the largest item is positioned at the root of the tree. The algorithm then replaces it with the last item of the heap and reduces the size of the heap by one.

3. After this, it heapifies the root of the tree and repeats the previous step, while the size of the heap is not one.

4. The process ensures that the previously picked maximum element is placed at its correct position in the sorted list, and this is repeated for all items in the list.