C Program: Implementing Heap sort with max Heap

Last update on December 20 2024 13:17:58 (UTC/GMT +8 hours)

Write a C program that uses the max heap data structure to implement heap sort. Show the sorting process on an array of integers.

Sample Solution:

C Code:

#include <stdio.h>

// Function to heapify a subtree rooted with node i, which is an index in arr[]
void maxHeapify(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 the found largest element with the root
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        // Recursively heapify the affected sub-tree
        maxHeapify(arr, n, largest);
    }
}

// Function to perform heap sort on an array
void heapSort(int arr[], int n) {
    // Build max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapify(arr, n, i);

    // Extract elements from the heap one by one
    for (int i = n - 1; i > 0; i--) {
        // Swap the root (max element) with the last element
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Call maxHeapify on the reduced heap
        maxHeapify(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");
}

int main() {
    // Test array
    int array[] = {14, 10, 0, 9, 15, 5, 7};
    int n = sizeof(array) / sizeof(array[0]);

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

    // Perform heap sort
    heapSort(array, n);

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

    return 0;
}

Output:

Original Array: 14 10 0 9 15 5 7
Sorted Array: 0 5 7 9 10 14 15

Explanation:

In the exercise above,

maxHeapify: This function takes an array, its size, and an index as input and ensures that the subtree rooted at that index maintains the max-heap property. It recursively swaps elements to ensure the largest element is at the root.
heapSort: This function performs heap sort on an array. It first builds a max heap from the array, then repeatedly extracts the maximum element (root) and calls maxHeapify on the reduced heap.
printArray: This function prints the elements of an array.
In the main function,

It initializes an array.
Prints the original array.
Calls heapSort to sort the array.
Prints the sorted array.

Flowchart:

C Programming Code Editor:

Previous: Construct Min Heap from random and sorted arrays.
Next: Implementing and testing Heapify function.