Question

Write a C program to implement the priority queue with the operations insert and extractmax.

Sample :

====Menu====

1. insert
2. extractmax
3. display
4. exit

Enter your choice: 1

Input a number: 2

enter any key to go to main menu

====Menu====

1. insert
2. extractmax
3. display
4. exit

Enter your choice: 1

Input a number: 4

enter any key to go to main menu

====Menu====

1. insert
2. extractmax
3. display
4. exit

Enter your choice: 1

Input a number: 6

enter any key to go to main menu

====Menu====

1. insert
2. extractmax
3. display
4. exit

Enter your choice: 2

enter any key to go to main menu

====Menu====

1. insert
2. extractmax
3. display
4. exit

Enter your choice: 3

Elements are : 2 4

enter any key to go to main menu

====Menu====

1. insert
2. extractmax
3. display
4. exit

Enter your choice: 4

bye

COMMENT COMPLETE CODE WITH EXPLANATION PLEASE. THANKS

Answer 1

// Priority Queue implementation in C

#include <stdio.h>
int size = 0;//global variable size
void swap(int *a, int *b) {//to swap elements
int temp = *b;
*b = *a;
*a = temp;
}

// Function to heapify the tree
void heapify(int array[], int size, int i) {
if (size == 1) {
    printf("Single element in the heap");
} else {
    // Find the largest among root, left child and right child
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && array[l] > array[largest])
      largest = l;
    if (r < size && array[r] > array[largest])
      largest = r;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
}
}

// Function to insert an element into the tree
void insert(int array[], int newNum) {
if (size == 0) {
    array[0] = newNum;
    size += 1;
} else {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--) {
      heapify(array, size, i);
    }
}
}

// Function to delete an element from the tree
void deleteRoot(int array[], int num) {
int i;
for (i = 0; i < size; i++) {
    if (num == array[i])
      break;
}

swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--) {
    heapify(array, size, i);
}
}

// Print the array
void printArray(int array[], int size) {
for (int i = size-1; i >=0; --i)
    printf("%d ", array[i]);
printf("\n");
}

// Driver code
int main() {
int array[20],n;
while(1)
{//creating the main menu option
      printf("\n==Main Menu==\n1.insert\n2.extractmax\n3.display\n4.exit\n");
      printf("Enter your choice:");
      scanf("%d",&n);
      if(n==1){
            int num;
            printf("Input a number:");
            scanf("%d",&num);
            insert(array,num);
      }
      else if(n==2)
            deleteRoot(array,array[0]);
      else if(n==3)
        {
            printf("Elements are:");
            printArray(array,size);
        }
      else if(n==4)
      {
          printf("\nbye");
          break;
      }
      printf("\nEnter any key to go to main menu");
}

}