C Program: Construct Max Heap from random and sorted arrays

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

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

Sample Solution:

C Code:

#include <stdio.h>          // Include the standard input/output library for printf function
#include <stdlib.h>         // Include the standard library for dynamic memory allocation

#define MAX_HEAP_SIZE 100   // Define the maximum size of the heap

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

// Function to maintain the max heap property after an element is inserted
void heapifyDown(int arr[], int size, int index) {
    int leftChild = 2 * index + 1;   // Calculate the left child index
    int rightChild = 2 * index + 2;  // Calculate the right child index
    int largest = index;              // Assume the current node is the largest

    // Find the largest element among the current node, left child, and right child
    if (leftChild < size && arr[leftChild] > arr[largest]) {
        largest = leftChild;
    }

    if (rightChild < size && arr[rightChild] > arr[largest]) {
        largest = rightChild;
    }

    // If the largest element is not the current node, swap with the largest child and continue heapifying down
    if (largest != index) {
        swap(&arr[index], &arr[largest]);
        heapifyDown(arr, size, largest);
    }
}

// Function to build a max heap from an array
void buildMaxHeap(int arr[], int size) {
    // Start from the last non-leaf node and heapify down to the root
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapifyDown(arr, size, i);
    }
}

// Function to display the elements of an array
void display(int arr[], int size) {
    printf("Array elements: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);  // Print each element in the array
    }
    printf("\n");
}

int main() {
    // Test with a random array
    int randomArray[] = {6, 8, 12, 7, 1};               // Declare a random array
    int randomSize = sizeof(randomArray) / sizeof(randomArray[0]);  // Calculate the size of the array

    printf("Original Random Array:\n");
    display(randomArray, randomSize);  // Display the original random array

    // Build max heap from the random array
    buildMaxHeap(randomArray, randomSize);

    printf("Max Heap from Random Array:\n");
    display(randomArray, randomSize);  // Display the max heap from the random array

    // Test with a sorted array
    int sortedArray[] = {19, 12, 8, 6, 2};              // Declare a sorted array
    int sortedSize = sizeof(sortedArray) / sizeof(sortedArray[0]);  // Calculate the size of the array

    printf("\nOriginal Sorted Array:\n");
    display(sortedArray, sortedSize);  // Display the original sorted array

    // Build max heap from the sorted array
    buildMaxHeap(sortedArray, sortedSize);

    printf("Max Heap from Sorted Array:\n");
    display(sortedArray, sortedSize);  // Display the max heap from the sorted array

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

Output:

Original Random Array:
Array elements: 6 8 12 7 1
Max Heap from Random Array:
Array elements: 12 8 6 7 1

Original Sorted Array:
Array elements: 19 12 8 6 2
Max Heap from Sorted Array:
Array elements: 19 12 8 6 2

Explanation:

In the exercise above,

Header and definitions:

Includes standard input/output and standard library headers.
Defines a constant MAX_HEAP_SIZE for the maximum size of the heap.

Swap function:

Define a swap function to exchange the values of two variables.

Heapify Down Function:

Implement heapifyDown to maintain the max heap property after deleting an element.
Compares the current node with its left and right children, swaps with the largest child if necessary, and recursively calls heapifyDown.

Build Max Heap Function:

Defines buildMaxHeap to construct a max heap from an array.
Iterates from the last non-leaf node to the root, calling heapifyDown to ensure the max heap property is satisfied.

Display Function:

Defines display to print array elements.

Main Function:

Test with a random array:

Initializes a random array.
Displays the original random array.
Builds a max heap from the random array.
Displays the max heap from the random array.

Test with a sorted array:

Initializes a sorted array.
Displays the original sorted array.
Builds a max heap from the sorted array.
Displays the max heap from the sorted array.

Flowchart:

C Programming Code Editor:

Previous: Basic Heap Operations - Insert, Delete, Display.
Next: Construct Max Heap from random and sorted arrays.