C Program: Construct Max Heap from random and sorted arrays

C Program to implement Heap: Exercise-2 with Solution

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.