lab3_priority_queue

#include <iostream>
#include <vector>

using namespace std;

const int SZ = 1e6 + 5;
const int INF = 1e9 + 5;

void heapify(int arr[], int n, int i) {

    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }

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

        heapify(arr, n, largest);
    }
}

struct priority_queue {
    int sz = 0;
    int arr[SZ];
};

void extract_min(priority_queue& q) {
    if (q.sz < 1) {
        cout << '*' << '\n';
        return;
    }
    int mn = q.arr[q.sz - 1];
    cout << mn << '\n';
    q.arr[q.sz - 1] = 0;
    q.sz--;
    heapify(q.arr, q.sz, 0);
}

void decrease_key(priority_queue& q, int x, int y) {
    q.arr[x - 1] = y;
    while (x > 0 && q.arr[(x - 1) / 2] < q.arr[x]) {
        swap(q.arr[x], q.arr[(x - 1) / 2]);
        x = (x - 1) / 2;
    }
}

void insert(priority_queue& q, int key) {
    q.sz++;
    q.arr[q.sz - 1] = INF;
    decrease_key(q, q.sz, key);
}

int main() {

    //freopen("priorityqueue.in", "r", stdin);
    //freopen("priorityqueue.out", "w", stdout);

    priority_queue q;
    string operation;a
    while (cin >> operation) {
        if (operation == "push") {
            int x;
            cin >> x;
            insert(q, x);
        }

        if (operation == "extract-min") {
            extract_min(q);
        }

        if (operation == "decrease-key") {
            int x, y;
            cin >> x >> y;

            decrease_key(q, x, y);
        }
    }
}