C Program: Construct Min Heap from random and sorted arrays

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

Write a C program function that constructs a min heap from an array of elements. Test it with both random and sorted input arrays.

Sample Solution:

C Code:

#include <stdio.h>

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

    // If left child is smaller than root
    if (left < n && arr[left] < arr[smallest])
        smallest = left;

    // If right child is smaller than smallest so far
    if (right < n && arr[right] < arr[smallest])
        smallest = right;

    // If smallest is not root
    if (smallest != i) {
        // Swap the found smallest element with the root
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;

        // Recursively heapify the affected sub-tree
        minHeapify(arr, n, smallest);
    }
}

// Function to build a min heap from an array
void buildMinHeap(int arr[], int n) {
    // Start from the last non-leaf node and heapify all nodes in reverse order
    for (int i = n / 2 - 1; i >= 0; i--)
        minHeapify(arr, n, i);
}

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

// Test the heap construction function
int main() {
    // Test with a random array
    int randomArray[] = {4, 10, 3, 5, 1};
    int n1 = sizeof(randomArray) / sizeof(randomArray[0]);

    printf("Original Random Array: ");
    printArray(randomArray, n1);

    // Build heap
    buildMinHeap(randomArray, n1);

    printf("Min Heap from Random Array: ");
    printArray(randomArray, n1);

    printf("\n");

    // Test with a sorted array
    int sortedArray[] = {8, 7, 5, 4, 2};
    int n2 = sizeof(sortedArray) / sizeof(sortedArray[0]);

    printf("Original Sorted Array: ");
    printArray(sortedArray, n2);

    // Build heap
    buildMinHeap(sortedArray, n2);

    printf("Min Heap from Sorted Array: ");
    printArray(sortedArray, n2);

    return 0;
}

Output:

Original Random Array: 4 10 3 5 1
Min Heap from Random Array: 1 4 3 5 10

Original Sorted Array: 8 7 5 4 2
Min Heap from Sorted Array: 2 4 5 8 7

Explanation:

In the exercise above,

minHeapify: This function takes an array, its size, and an index as input and ensures that the subtree rooted at that index maintains the min-heap property.
buildMinHeap: This function builds a min-heap from an array by calling minHeapify on each non-leaf node in reverse order.
printArray: This function prints the elements of an array.
In the main function:

It tests the buildMinHeap() function with a randomly ordered array (randomArray) and prints the original array and the resulting min-heap.
It does the same with a sorted array (sortedArray).

Flowchart:

C Programming Code Editor:

Previous: Construct Max Heap from random and sorted arrays.
Next: Implementing Heap sort with max Heap.