C Program: Merge two Heaps into a single max Heap

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

Write a C program that creates a function to merge two heaps into a single heap. Please make sure that the resulting heap satisfies the heap property.

Sample Solution:

C Code:

#include <stdio.h>

#define MAX_SIZE 100

// Structure to represent a heap
struct Heap {
    int array[MAX_SIZE]; // Array to store elements in the heap
    int size;            // Current 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 heapify a subtree rooted with node i
void maxHeapify(struct Heap* heap, int i) {
    int largest = i;    // Initialize largest as the root
    int left = 2 * i + 1; // Calculate index of the left child
    int right = 2 * i + 2; // Calculate index of the right child

    // If left child is larger than root
    if (left < heap->size && heap->array[left] > heap->array[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < heap->size && heap->array[right] > heap->array[largest])
        largest = right;

    // If largest is not root
    if (largest != i) {
        // Swap the found largest element with the root
        swap(&heap->array[i], &heap->array[largest]);

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

// Function to build a max heap
void buildMaxHeap(struct Heap* heap) {
    // Start from the last non-leaf node and heapify all nodes in reverse order
    for (int i = heap->size / 2 - 1; i >= 0; i--) {
        maxHeapify(heap, i);
    }
}

// Function to create a heap from an array
struct Heap createHeap(int arr[], int n) {
    struct Heap newHeap;
    newHeap.size = n;

    for (int i = 0; i < n; i++) {
        newHeap.array[i] = arr[i];
    }

    buildMaxHeap(&newHeap);

    return newHeap;
}

// Function to merge two heaps into a single heap
struct Heap mergeHeaps(struct Heap* heap1, struct Heap* heap2) {
    struct Heap mergedHeap;
    mergedHeap.size = heap1->size + heap2->size;

    // Copy elements from heap1 and heap2 into mergedHeap
    for (int i = 0; i < heap1->size; i++) {
        mergedHeap.array[i] = heap1->array[i];
    }

    for (int i = 0; i < heap2->size; i++) {
        mergedHeap.array[heap1->size + i] = heap2->array[i];
    }

    // Build max heap for the mergedHeap
    buildMaxHeap(&mergedHeap);

    return mergedHeap;
}

// Function to print the heap
void printHeap(struct Heap* heap) {
    printf("Heap: ");
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->array[i]);
    }
    printf("\n");
}

int main() {
    int arr1[] = {11, 6, 14, 3, 10};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    int arr2[] = {20, 8, 24, 5, 15};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

    // Create heaps from the arrays
    struct Heap heap1 = createHeap(arr1, n1);
    struct Heap heap2 = createHeap(arr2, n2);

    printf("Heap 1: ");
    printHeap(&heap1);

    printf("Heap 2: ");
    printHeap(&heap2);

    // Merge the heaps
    struct Heap mergedHeap = mergeHeaps(&heap1, &heap2);

    printf("Merged Heap: ");
    printHeap(&mergedHeap);

    return 0;
}

Output:

Heap 1: Heap: 14 10 11 3 6
Heap 2: Heap: 24 15 20 5 8
Merged Heap: Heap: 24 20 15 10 8 11 14 3 5 6

Explanation:

In the exercise above,

Struct Definition:

struct Heap: Represents a heap using an array. It contains an array to store elements (array) and the current size of the heap (size).

Utility Functions:

swap: Swaps two elements in the heap.
maxHeapify: Ensures a subtree rooted at a given index maintains the max-heap property.
buildMaxHeap: Constructs a max heap from an array.
createHeap: Creates a heap from an array and builds the max heap.
mergeHeaps: Merges two heaps into a single heap while maintaining the max-heap property.
printHeap: Prints the elements in the heap.

Main Function:

Initializes two heaps (heap1 and heap2) from different arrays.
Prints the original heaps.
Merges the heaps into a new heap (mergedHeap) and prints the merged heap.

Flowchart:

C Programming Code Editor:

Previous: Priority Queue using max Heap - Enqueue and Dequeue operations.
Next: Implementing decreaseKey in maximum Heap.