Envío 6644

Código

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class MyHeap {
    vector<pair<int, string>> data;
    void heapifyUp(int index);
    void heapifyDown(int index);
    int parent(int index);
    int leftChild(int index);
    int rightChild(int index);

public:
    MyHeap();
    void insert(int priority, string name);
    string getMax();
    void popMax();
    int length;
};

MyHeap::MyHeap() {
    vector<pair<int, string>> tmp(10, make_pair(-1, ""));
    this->length = 0;
    this->data = tmp;
}
int MyHeap::parent(int index) {
    return (index - 1) / 2;
}
int MyHeap::leftChild(int index) {
    return index * 2 + 1;
}
int MyHeap::rightChild(int index) {
    return  index * 2 + 2;
}
void MyHeap::heapifyUp(int index) {
    if(index == 0) {
        return;
    }

    int p = this->parent(index);
    pair<int, string> parentValues = this->data[p];
    pair<int, string> currValues = this->data[index];

    if((parentValues.first < currValues.first) ||
    (parentValues.first == currValues.first && currValues.second < parentValues.second)) {
        this->data[index] = parentValues;
        this->data[p] = currValues;
        this->heapifyUp(p);
    }
}

void MyHeap::heapifyDown(int index) {
    int leftIndex = this->leftChild(index);
    int rightIndex = this->rightChild(index);
    if(index >= this->length || leftIndex >= this->length) {
        return;
    }

    pair<int, string> leftValues = make_pair(-1, "X");
    pair<int, string> rightValues = make_pair(-1, "X");

    if(leftIndex <= this->length) {
        leftValues = this->data[leftIndex];
    }
    if(rightIndex <= this->length) {
        rightValues = this->data[rightIndex];
    }
    pair<int, string> currValues = this->data[index];

    if((leftValues.first > rightValues.first && leftValues.first > currValues.first && leftValues.second != "X")
    || (leftValues.first == currValues.first && leftValues.second < currValues.second && leftValues.second != "X")) {
        this->data[index] = leftValues;
        this->data[leftIndex] = currValues;
        this->heapifyDown(leftIndex);
    } else if((rightValues.first > leftValues.first && rightValues.first > currValues.first && rightValues.second != "X")
    || (rightValues.first == currValues.first && rightValues.second < currValues.second && rightValues.second != "X")) {
        this->data[index] = rightValues;
        this->data[rightIndex] = currValues;
        this->heapifyDown(rightIndex);
    }
}
void MyHeap::insert(int priority, std::string name) {
    this->data[this->length] = make_pair(priority, name);
    this->heapifyUp(this->length);
    this->length++;
}
string MyHeap::getMax() {
    return this->data[0].second;
}
void MyHeap::popMax() {
    this->length--;
    if(this->length == 0) {
        this->data.clear();
        return;
    }
    this->data[0] = this->data[this->length];
    this->heapifyDown(0);
    return;
}


int main() {
    int n; cin>>n;
    MyHeap heap;
    while(n--) {
        string op; cin>>op;
        string x; int p;
        if(op == "Insert") {
            cin>>x>>p;
            heap.insert(p, x);
        } else if(op == "GetMax") {
            cout<<heap.getMax()<<endl;
        } else {
            heap.popMax();
        }
    }
    return 0;
}