C Program: Implementing Heap sort with max Heap

C Program to implement Heap: Exercise-4 with Solution

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.