Heap Sort Program in C, C++, and Java | Examples & Explanation

Heap Sort is a comparison-based sorting technique that uses a binary heap data structure. It works by building a max heap and repeatedly extracting the largest element from the heap until the array is sorted.

Steps of Heap Sort Algorithm

1. Build a Max Heap: Convert the input array into a max heap (where the largest element is at the root).
2. Extract the Maximum Element: Swap the root with the last element and reduce the heap size.
3. Heapify the Root: Restore the heap property by heapifying the root.
4. Repeat: Continue extracting the max element and heapifying until the array is sorted.

Heap Sort Implementation in C

cCopyEdit#include <stdio.h>

// Function to heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

// Function to perform Heap Sort
void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver code
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Heap Sort Implementation in C++

cppCopyEdit#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at index i
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// Function to perform Heap Sort
void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Heap Sort Implementation in Java

javaCopyEditimport java.util.Arrays;

public class HeapSort {
    public void heapify(int arr[], int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        if (left < n && arr[left] > arr[largest])
            largest = left;

        if (right < n && arr[right] > arr[largest])
            largest = right;

        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n, largest);
        }
    }

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

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

        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            heapify(arr, i, 0);
        }
    }

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

        HeapSort ob = new HeapSort();
        ob.heapSort(arr);

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

Time and Space Complexity

• Best Case: When the array is already sorted, it still takes O(n log n) time.
• Worst Case: When the array is in descending order, it still takes O(n log n).
• Space Complexity: O(1) (Heap Sort is an in-place sorting algorithm).

Advantages of Heap Sort

Efficiency: Performs consistently in O(n log n) time.
In-Place Sorting: Does not require extra space like Merge Sort.
No Worst-Case Degradation: Unlike Quick Sort, Heap Sort does not suffer from O(n²) worst-case performance.

Disadvantages of Heap Sort

Not Stable: It may change the relative order of equal elements.
Heap Construction Overhead: The process of heapifying adds some extra computation compared to Quick Sort.

Conclusion

Heap Sort is an efficient, comparison-based sorting algorithm suitable for large datasets. It is commonly used in scenarios where worst-case performance must be guaranteed. However, it is less popular than Quick Sort due to slightly higher constant factors in practice.