C Program: Implementing decreaseKey in maximum Heap

C Program to implement Heap: Exercise-8 with Solution

Write a C program that implements the decreaseKey operation in a maximum heap. Check the function by decreasing the key of a node and validating the heap property.

Sample Solution:

C Code:

#include <stdio.h>

#define MAX_SIZE 100

// Structure to represent a maximum heap
struct MaxHeap {
    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 MaxHeap* 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 MaxHeap* 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 maximum heap from an array
struct MaxHeap createMaxHeap(int arr[], int n) {
    struct MaxHeap newHeap;
    newHeap.size = n;

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

    // Build max heap from the array
    buildMaxHeap(&newHeap);

    return newHeap;
}

// Function to perform the decreaseKey operation on a maximum heap
void decreaseKey(struct MaxHeap* heap, int i, int newKey) {
    if (i < 0 || i >= heap->size) {
        printf("Invalid index\n");
        return;
    }

    if (newKey > heap->array[i]) {
        printf("New key is greater than the current key\n");
        return;
    }

    // Update the key at the specified index
    heap->array[i] = newKey;

    // Move the modified key up the heap to maintain the max-heap property
    while (i > 0 && heap->array[(i - 1) / 2] < heap->array[i]) {
        swap(&heap->array[i], &heap->array[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

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

// Main function
int main() {
    int arr[] = {10, 22, 15, 22, 30};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Create a maximum heap from the array
    struct MaxHeap maxHeap = createMaxHeap(arr, n);

    printf("Original ");
    printMaxHeap(&maxHeap);

    // Decrease the key at index 2 to 5
    decreaseKey(&maxHeap, 2, 5);

    printf("After Decrease Key at index 2 to 5: ");
    printMaxHeap(&maxHeap);

    return 0;
}

Output:

Original Max Heap: 30 22 15 10 22
After Decrease Key at index 2 to 5: Max Heap: 30 22 5 10 22

Explanation:

In the exercise above,

• Struct Definition:
• struct MaxHeap: Represents a maximum heap using an array. It includes the 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.
• createMaxHeap: Creates a max heap from an array and builds the max heap.
• decreaseKey: Decreases the key at a specified index in the max heap and adjusts the heap to maintain the max-heap property.
• printMaxHeap: Prints the elements in the max heap.
• Main Function:
• Initializes a max heap from an array.
• Prints the original max heap.
• Performs the decreaseKey operation on the max heap at index 2, reducing the key to 5.
• Prints the max heap after the decrease key operation.

Flowchart:

C Programming Code Editor:

Previous: Merge two Heaps into a single max Heap.
Next: Finding Kth largest element with max Heap.