C Program: Implementing decreaseKey in maximum Heap

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

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.