#include <iostream>
#define  INFINITY 99999999
using namespace std;

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
class MaxPq{
    int initSize;
    int MaxSize;
    int *arr;
    int length;


public:
    MaxPq();


    void Insert(int x);
    int FindMax();
    int ExtractMax();
    void IncreaseKey(int i, int newKey);
    void DecreaseKey(int i, int newKey);
    void Print();


    int FindElement(int n);
    void Heapify(int i);
    int getRight(int i);
    int getLeft(int i);
    int getParent(int i);
};

int main()
{
    int choice;
    MaxPq q;

    while(1){
        cout<<"1. Insert"<<endl;
        cout<<"2. Find Max"<<endl;
        cout<<"3. Extract Max"<<endl;
        cout<<"4. Increase Key"<<endl;
        cout<<"5. Decrease Key"<<endl;
        cout<<"6. Print"<<endl;
        cout<<"7. Quit"<<endl;
        cout<<"Enter Your Choice"<<endl;
        cin>>choice;
        if(choice==1){
            int n;
            cout<<"Enter the number"<<endl;
            cin>>n;
            q.Insert(n);
        }
        else if (choice==2){
            int max = q.FindMax();
            cout<<"Max Element is: "<<max<<endl;
        }
        else if(choice==3){
            int max = q.ExtractMax();
            cout<<"Max = "<<max<<endl;
            cout<<"Max Extracted"<<endl;
        }
        else if (choice == 4){
            int i , key;
            cout<<"Enter Position"<<endl;
            int n = q.FindElement(i);
            cout<<"Element in "<<i<<"th position is "<<n<<endl;
            cout<<"Enter new value : ";
            cin>>key;
            q.IncreaseKey(i, key);
            //q.Heapify(i);
        }
        else if (choice == 5){
            int i , key;
            cout<<"Enter Position"<<endl;
            int n = q.FindElement(i);
            cout<<"Element in "<<i<<"th position is "<<n<<endl;
            cout<<"Enter new value : ";
            cin>>key;
            q.DecreaseKey(i, key);
            //q.Heapify();
        }
        else if(choice == 6){
            cout<<"The Queue is"<<endl;
            q.Print();
        }
        else if(choice == 7){
            cout<<"Quiting program"<<endl;
            break;
        }
    }
}


MaxPq::MaxPq() {
    initSize = 10;
    MaxSize = initSize;
    arr = new int[MaxSize];
    length = 0;

}

void MaxPq::Insert(int x) {
    if (length >= MaxSize ){
        arr = (int*) realloc(arr, sizeof(int)*(MaxSize+10));
        MaxSize = MaxSize+10;
        length = length+1;
        arr[length] = -INFINITY;
        IncreaseKey(length, x);
    }
    else{
        length = length+1;
        arr[length] = -INFINITY;
        IncreaseKey(length, x);

    }

}

int MaxPq::ExtractMax() {
    int max = arr[1];
    arr[1] = arr[length];
    length--;
    Heapify(1);
    return max;
}

int MaxPq::FindMax() {
    return arr[1];
}

void MaxPq::IncreaseKey(int i, int newKey) {
    arr[i] = newKey;
    while (i>1 && arr[getParent(i)]<arr[i]){
        swap(arr[i],arr[getParent(i)]);
        i = getParent(i);
    }

}

void MaxPq::DecreaseKey(int i, int newKey) {
    arr[i] = newKey;
    Heapify(i);

}

void MaxPq::Print() {
    for (int i = 1; i <=length ; i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;

}

int MaxPq::FindElement(int n) {
    for (int i = 1; i <=length ; ++i) {
        if (arr[i]==n)
            return i;
    }
    return -1;
}

void MaxPq::Heapify(int i) {
    int largest = i;
    int left = getLeft(i);
    int right = getRight(i);

    if (left <= length && left>0){
        if (arr[left]>arr[i]){
            largest = left;
        }
    }
    if (right<=length && right>0){
        if(arr[right]>arr[largest]){
            largest = right;
        }
    }

    if (largest != i){
        swap(&arr[i],&arr[largest]);
        Heapify(largest);
    }

}

int MaxPq::getParent(int i) {
    if(i> 1 && i<length)
        return i/2;
    return -1;
}

int MaxPq::getRight(int i) {
    if(((2*i)+1)<length && i>=1)
        return (2*i)+1;
    return -1;
}

int MaxPq::getLeft(int i) {
    if((2*i)<length && i>=1)
        return 2*i;
    return 0;
}