C Program to Implement Heap Sort

Introduction

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It’s an in-place, non-stable sorting algorithm with a time complexity of O(n log n). The algorithm builds a max-heap from the input data and then repeatedly extracts the maximum element (which is at the root) and rebuilds the heap until all elements are sorted.

Example:

• Input: Unsorted array [4, 10, 3, 5, 1]
• Output: Sorted array [1, 3, 4, 5, 10]

Problem Statement

Create a C program that:

• Implements the Heap Sort algorithm to sort an array.
• Takes an unsorted array as input and outputs the sorted array.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> for standard input-output functions.
2. Implement the Heapify Function: This function ensures that a subtree rooted at a given index satisfies the heap property.
3. Implement the Heap Sort Function: This function builds the heap and then sorts the array.
4. Create a Main Function: Allow the user to input the array, apply heap sort, and display the sorted array.

C Program to Implement Heap Sort

#include <stdio.h>

// Function to swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify a subtree rooted with node i, which is an index in arr[].
void heapify(int arr[], int n, int i) {
    int largest = i;  // Initialize largest as root
    int left = 2 * i + 1;  // left child
    int right = 2 * i + 2;  // right child

    // 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) {
        swap(&arr[i], &arr[largest]);

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

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

    // One by one extract elements from heap
    for (int i = n - 1; i >= 0; i--) {
        // Move current root to end
        swap(&arr[0], &arr[i]);

        // Call heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

int main() {
    int n;

    // Input the size of the array
    printf("Enter the number of elements in the array: ");
    scanf("%d", &n);

    int arr[n];

    // Input the elements of the array
    printf("Enter %d elements:\n", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Apply Heap Sort
    heapSort(arr, n);

    // Output the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Function to Swap Two Elements

• The swap function exchanges the values of two variables using a temporary variable.

Function to Heapify a Subtree

• The heapify function ensures that the subtree rooted at a given index i satisfies the heap property. If the root is not the largest element, it swaps the root with the largest child and then recursively heapifies the affected subtree.

Function to Implement Heap Sort

• The heapSort function first builds a max heap by calling heapify on all non-leaf nodes.
• After building the heap, the function repeatedly extracts the largest element (the root of the heap) by swapping it with the last element and then reducing the heap size by one. It then heapifies the reduced heap to maintain the heap property.

Main Function

• The main function allows the user to input the size of the array and the elements.
• It then applies Heap Sort to the array and displays the sorted array.

Output Example

Example Output:

Enter the number of elements in the array: 5
Enter 5 elements:
4 10 3 5 1
Sorted array: 1 3 4 5 10

Example Output (Already Sorted):

Enter the number of elements in the array: 6
Enter 6 elements:
1 2 3 4 5 6
Sorted array: 1 2 3 4 5 6

Conclusion

This C program demonstrates how to implement Heap Sort, a popular sorting algorithm known for its efficiency and in-place sorting capability. Heap Sort is particularly useful when a stable sort is not required, and it provides a reliable O(n log n) time complexity, making it suitable for large datasets. This program is a practical example of heap operations and sorting in C programming.