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

#define MAX 50

int heap[MAX];
int heapSize = 0;

// Function to insert an item into max heap
void insert(int item) {
    int i;

    if (heapSize == MAX - 1) {
        printf("Heap is full. Cannot insert.\n");
        return;
    }

    // First insert at last position
    heapSize++;
    i = heapSize;

    // Percolate up
    while (i > 1 && item > heap[i / 2]) {
        heap[i] = heap[i / 2];  // move parent down
        i = i / 2;              // move up
    }

    heap[i] = item;
    printf("Inserted %d into heap.\n", item);
}

// Function to delete max (root) from heap
int deleteMax() {
    int i, child;
    int item, last;

    if (heapSize == 0) {
        printf("Heap is empty. Cannot delete.\n");
        return -1;
    }

    item = heap[1];          // max element
    last = heap[heapSize];   // last element
    heapSize--;

    i = 1;

    // Percolate down
    while (2 * i <= heapSize) {
        // left child
        child = 2 * i;

        // choose larger child if right child exists
        if (child < heapSize && heap[child + 1] > heap[child])
            child++;

        if (last >= heap[child])
            break;

        heap[i] = heap[child];  // move child up
        i = child;
    }

    heap[i] = last;

    return item;
}

// Display heap contents (array form)
void display() {
    int i;

    if (heapSize == 0) {
        printf("Heap is empty.\n");
        return;
    }

    printf("Heap contents (array form):\n");
    for (i = 1; i <= heapSize; i++)
        printf("%d ", heap[i]);
    printf("\n");
}

int main() {
    int choice, item, deleted;

    while (1) {
        printf("\n=== MAX HEAP (PRIORITY QUEUE) MENU ===\n");
        printf("1. Insert\n");
        printf("2. Delete Max\n");
        printf("3. Display Heap\n");
        printf("4. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch (choice) {
        case 1:
            printf("Enter item to insert: ");
            scanf("%d", &item);
            insert(item);
            break;

        case 2:
            deleted = deleteMax();
            if (deleted != -1)
                printf("Deleted item (max): %d\n", deleted);
            break;

        case 3:
            display();
            break;

        case 4:
            printf("Exiting...\n");
            exit(0);

        default:
            printf("Invalid choice. Try again.\n");
        }
    }

    return 0;
}