#include <bits/stdc++.h>

using namespace std;

struct StudentInfo{
    string name;
    double CGPA;
    int roll;
};

struct Node{
    StudentInfo student;
    Node* left;
    Node* right;
};

void menu();

void heapify(StudentInfo * student,int val,int total);

bool push(StudentInfo * student, StudentInfo newStudent, int infoCap, int * cntr);

StudentInfo extractMax(StudentInfo * student,int * cntr);

void insertData(Node ** root,Node * newNode);

void printSortedData(Node * root);

int main()
{
    int infoCap = 100;
    int cntr = 0;
    int input=1;
    StudentInfo student[105];
    while(input)
    {
        menu();
        cin>>input;
        if(input == 1)
        {
            StudentInfo newStudent;
            cout<<"Enter name"<<endl;
            cin>>newStudent.name;
            cout<<"Enter CGPA"<<endl;
            cin>>newStudent.CGPA;
            cout<<"Enter roll"<<endl;
            cin>>newStudent.roll;
            if(!push(student,newStudent,infoCap,&cntr)) cout<<"Priority queue is full"<<endl;
        }
        else if(input == 2)
        {
            if(cntr >0)
            {
                StudentInfo maxStudent;
                maxStudent = extractMax(student,&cntr);
                cout<<"Name : "<<maxStudent.name<<endl;
                cout<<"CGPA : "<<maxStudent.CGPA<<endl;
                cout<<"Roll : "<<maxStudent.roll<<endl;
            }
            else cout<<"Queue empty"<<endl;
        }
        else if(input == 3)
        {
            Node * root = new Node;
            root =  NULL;
            for(int i = 1; i <=cntr;i++)
            {
                Node * newNode = new Node;
                newNode->left = NULL;
                newNode->right = NULL;
                newNode->student.name = student[i].name;
                newNode->student.CGPA = student[i].CGPA;
                newNode->student.roll = student[i].roll;
                insertData(&root,newNode);
            }
            printSortedData(root);
        }
    }

    return 0;
}

void menu()
{
    cout<<"Enter 1 to push new data"<<endl;
    cout<<"Enter 2 to pop maximum value"<<endl;
    cout<<"Enter 3 show sorted data"<<endl;
}

void heapify(StudentInfo * student,int val,int total)
{
    int left = 2*val;
    int right = 2*val +1;
    int maxVal=1;
    if(left<=total && student[left].CGPA > student[val].CGPA) maxVal = left;
    else maxVal = val;
    if(right<=total &&student[right].CGPA > student[val].CGPA) maxVal = right;
    if(maxVal != val)
    {
        StudentInfo temp = student[maxVal];
        student[maxVal] = student[val];
        student[val] = temp;
        heapify(student, maxVal,total);
    }
}

bool push(StudentInfo * student, StudentInfo newStudent, int infoCap, int * cntr)
{
    if(*cntr >= infoCap) return false;
    student[++(*cntr)] = newStudent;
    for(int i=(*cntr)/2;i>0;i--) heapify(student,i,*cntr);
    return true;
}

StudentInfo extractMax(StudentInfo * student,int * cntr)
{
    StudentInfo newStudent;
    newStudent = student[1];
    StudentInfo temp = student[*cntr];
    (*cntr)--;
    student[1] = temp;
    for(int i=(*cntr)/2;i>0;i--) heapify(student,i,*cntr);
    return newStudent;
}

void insertData(Node ** root,Node * newNode)
{
    if(*root == NULL)
    {
        *root =  newNode;
    }
    else
    {
        if(newNode->student.CGPA < (*root)->student.CGPA) insertData(&((*root)->left),newNode);
        else insertData(&((*root)->right),newNode);
    }
}

void printSortedData(Node * root)
{
    if(root == NULL) return ;

    printSortedData(root->left);
    cout<<"Name : "<<root->student.name<<endl;
    cout<<"CGPA : "<<root->student.CGPA<<endl;
    cout<<"Roll : "<<root->student.roll<<endl;

    printSortedData(root->right);
}