█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 6644

Problema 0xb0 - Implementar una cola de prioridad

  • Autor: carrillodev
  • Fecha: 2022-09-23 06:08:26 UTC (Hace 11 días)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.004 s 6 KBi
#2
Correcto
0.005 s 1 KBi
#3
Correcto
0.005 s 3 KBi
#4
Correcto
0.008 s 4 KBi
#5
Correcto
0.005 s 2 KBi
#6
Incorrecto
0.006 s 1 KBi
#7
Correcto
0.006 s 1 KBi
#8
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.005 s 1 KBi
#9
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.006 s 1 KBi
#10
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.006 s 1 KBi
#11
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.006 s 1 KBi
#12
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.006 s 1 KBi
#13
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.005 s 1 KBi
#14
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.005 s 1 KBi
#15
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.005 s 1 KBi
#16
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.006 s 1 KBi
#17
Error en tiempo de ejecución (NZEC)
Exited with error status 139
run: line 1:     3 Segmentation fault      (core dumped) ./a.out
0.007 s 1 KBi
Puntos totales: 36 / 100

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;
}