Heap Sort in Java for Competitive Programming

What is Heap Sort?

Heap sort is a comparison-based sorting algorithm that relies on the Heap data structure. It's known for its performance guarantee of O(n log n) in both average and worst-case scenarios, making it a suitable choice in situations where you need a predictable and efficient sorting algorithm, particularly for larger datasets. Heap sort is an in-place algorithm (requires minimal extra space) which can be beneficial when memory usage is a concern.

Understanding the Heap Data Structure

A heap is a specialized tree-based data structure that satisfies the heap property. It's typically represented as a complete binary tree, although conceptually it can be any tree adhering to heap rules. There are two main types of heaps:

• Max Heap: In a max heap, the value of each node is greater than or equal to the value of its children. The largest element is always at the root.
• Min Heap: In a min heap, the value of each node is less than or equal to the value of its children. The smallest element is always at the root.

For heap sort, we primarily use the max heap. A complete binary tree can efficiently be represented using an array. The children of a node at index i are located at indices 2*i + 1 and 2*i + 2. The parent of a node at index i is located at (i - 1) / 2 (integer division).

Heap Sort Algorithm: Explanation

Heap sort involves two main phases:

1. Build Heap: Transform the input array into a max heap. This is done by iterating through the array (from the middle towards the beginning) and "heapifying" each node. Heapifying means ensuring that the subtree rooted at a particular node satisfies the max heap property.
2. Sort: Repeatedly extract the maximum element (which is at the root of the heap) and place it at the end of the sorted portion of the array. After each extraction, the heap is restructured to maintain the max heap property.

Here's a breakdown of the steps:

1. Build Max Heap:
   • Start from the middle of the array and work your way to the beginning.
   • For each element, call a heapify function to ensure that the element and its children satisfy the max heap property.
2. Sorting Phase:
   • Swap the root element (maximum) with the last element in the heap.
   • Reduce the heap size by 1.
   • Call heapify on the new root element to maintain the max heap property.
   • Repeat until the heap size is 1.

Heap Sort Implementation in Java

Here's a Java implementation of the Heap Sort algorithm, suitable for competitive programming scenarios:

 public class HeapSort {

    public static 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--) {
            // Swap current root with end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify 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 left = 2 * i + 1;
        int 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};
        sort(arr);
        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
} 

Explanation of the Java Code:

• sort(int[] arr): This is the main function that performs the heap sort.
• heapify(int[] arr, int n, int i): This function maintains the heap property. It assumes that the subtrees rooted at the children of node i are already heaps. It finds the largest element among the node i and its children and swaps it with node i if necessary. Then, it recursively calls heapify on the affected subtree.
• The main function demonstrates how to use the sort function with a sample array.

Competitive Programming Example and Solution

Let's consider a problem from a competitive programming platform that can be solved using Heap Sort:

Problem: Given an array of integers, sort the array in ascending order.

 import java.util.*;
import java.lang.*;

class Solution {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        HeapSort.sort(arr);  //Using the previously defined HeapSort class

        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        scanner.close();
    }
} 

Time and Space Complexity

• Time Complexity: O(n log n) in all cases (best, average, and worst).
• Space Complexity: O(1) - Heap Sort is an in-place algorithm. It requires only a constant amount of extra space.

Advantages and Disadvantages

Advantages:

• Guaranteed O(n log n) time complexity.
• In-place sorting algorithm.

Disadvantages:

• Not as cache-friendly as some other algorithms (like Merge Sort).
• Can be slightly slower than Quick Sort in practice for some datasets, although Quick Sort has a worst-case O(n²) time complexity.