Example: Heap Sort using Recursion in C

// Heap Sort using Recursion
#include <stdio.h>

// Function to maintain the heap property in a subtree rooted at index i.
// n is the size of the heap.
void heapify(int arr[], int n, int i) {
    // Step 1: Initialize 'largest' as the root of the current subtree
    int largest = i;
    // Calculate indices of left and right children
    int left = 2 * i + 1; // Left child index
    int right = 2 * i + 2; // Right child index

    // Step 2: Check if the left child exists and is greater than the current largest
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // Step 3: Check if the right child exists and is greater than the current largest
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // Step 4: If the largest element is not the current root, swap them
    // and recursively heapify the affected subtree.
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // Recursively call heapify on the subtree that was affected by the swap
        heapify(arr, n, largest);
    }
}

// Main function to perform heap sort on an array of size n
void heapSort(int arr[], int n) {
    // Step 1: Build a max-heap (rearrange the array)
    // We start from the last non-leaf node (n/2 - 1) and go up to the root (0).
    // This ensures that when heapify is called on a node, its children are already heaps.
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Step 2: Extract elements one by one from the heap
    // After building the heap, the largest element is at arr[0].
    // We swap it with the last element, reduce the heap size, and re-heapify.
    for (int i = n - 1; i > 0; i--) {
        // Move the current root (largest element) to the end of the array
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Call heapify on the reduced heap (excluding the last element which is now sorted)
        // to maintain the max-heap property for the remaining elements.
        heapify(arr, i, 0);
    }
}

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

int main() {
    // Step 1: Define an example array to be sorted
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    // Step 2: Perform heap sort using the defined function
    heapSort(arr, n);

    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}