Implement Binary Heap

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *array; // Pointer to the array of heap elements
    int size;   // Current size of the heap
    int capacity; // Maximum capacity of the heap
} MaxHeap;

// Function to create a MaxHeap
MaxHeap* createHeap(int capacity) {
    MaxHeap* maxHeap = (MaxHeap*)malloc(sizeof(MaxHeap));
    maxHeap->capacity = capacity;
    maxHeap->size = 0;
    maxHeap->array = (int*)malloc(capacity * sizeof(int));
    return maxHeap;
}

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

// Function to heapify a subtree rooted at index i
void heapify(MaxHeap* maxHeap, int index) {
    int largest = index; // Initialize largest as root
    int left = 2 * index + 1; // left = 2*i + 1
    int right = 2 * index + 2; // right = 2*i + 2

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

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

    // If largest is not root
    if (largest != index) {
        swap(&maxHeap->array[index], &maxHeap->array[largest]);
        heapify(maxHeap, largest); // Recursively heapify the affected subtree
    }
}

// Function to insert a new key
void insert(MaxHeap* maxHeap, int key) {
    if (maxHeap->size == maxHeap->capacity) {
        printf("Heap is full. Cannot insert %d\n", key);
        return;
    }

    // Insert the new key at the end
    maxHeap->array[maxHeap->size] = key;
    maxHeap->size++;

    // Fix the max heap property if it's violated
    for (int i = (maxHeap->size / 2) - 1; i >= 0; i--) {
        heapify(maxHeap, i);
    }
}

// Function to delete the maximum element (root)
int deleteMax(MaxHeap* maxHeap) {
    if (maxHeap->size <= 0) {
        return -1; // Heap is empty
    }
    if (maxHeap->size == 1) {
        maxHeap->size--;
        return maxHeap->array[0]; // Only one element left
    }

    // Store the maximum value, and remove it from heap
    int root = maxHeap->array[0];
    maxHeap->array[0] = maxHeap->array[maxHeap->size - 1];
    maxHeap->size--;
    heapify(maxHeap, 0); // Call heapify on the root

    return root;
}

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

// Main function to demonstrate the heap operations
int main() {
    MaxHeap* maxHeap = createHeap(10);

    // Inserting elements
    insert(maxHeap, 3);
    insert(maxHeap, 1);
    insert(maxHeap, 14);
    insert(maxHeap, 7);
    insert(maxHeap, 9);
    insert(maxHeap, 10);
    insert(maxHeap, 4);

    printf("Max Heap: ");
    printHeap(maxHeap);

    // Deleting the maximum element
    printf("Deleted maximum element: %d\n", deleteMax(maxHeap));
    printf("Max Heap after deletion: ");
    printHeap(maxHeap);

    // Free allocated memory
    free(maxHeap->array);
    free(maxHeap);
    return 0;
}