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

void heapify(int array[], int size, int i);
void swap(int *a, int *b);
void printArray(int array[], int size);
void insert(int array[], int newNum);
void deleteRoot(int array[], int *size);

// Global variable for tracking the size of the heap
int size = 0;

int main(void) {
    int array[10];

    // Inserting elements into the heap
    insert(array, 3);
    insert(array, 4);
    insert(array, 9);
    insert(array, 5);
    insert(array, 2);

    // Printing the Max-Heap
    printf("Max-Heap array: ");
    printArray(array, size);

    // Deleting the root element
    deleteRoot(array, &size);
    printf("After deleting an element: ");
    printArray(array, size);

    return 0;
}

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

// Function to heapify the array
void heapify(int array[], int size, int i) {
    int largest = i; // Initialize largest as root
    int left = 2 * i + 1; // Left child
    int right = 2 * i + 2; // Right child

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

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

    // If largest is not root
    if (largest != i) {
        swap(&array[i], &array[largest]);
        // Recursively heapify the affected sub-tree
        heapify(array, size, largest);
    }
}

// Function to insert a new element into the heap
void insert(int array[], int newNum) {
    array[size] = newNum; // Insert the new element at the end
    int current = size;
    size++;

    // Fix the Max Heap property if it's violated
    while (current != 0 && array[(current - 1) / 2] < array[current]) {
        swap(&array[(current - 1) / 2], &array[current]);
        current = (current - 1) / 2;
    }
}

// Function to delete the root element from the heap
void deleteRoot(int array[], int *size) {
    if (*size <= 0) {
        printf("Heap is empty!\n");
        return;
    }

    // Replace root with the last element
    array[0] = array[*size - 1];
    (*size)--;

    // Heapify the root
    heapify(array, *size, 0);
}

// Function to print the array
void printArray(int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}