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

void izpisi(vector<int> v) {
    for (int x : v) cout << x << " ";
    cout << endl;
}

class BinaryHeap {
private:
    vector<int> t={-1};
public:
    void push(int x) {
        t.push_back(x);
        int i=t.size()-1;
        while (i>1 && t[i]<t[i/2]) {
            swap(t[i],t[i/2]);
            i/=2;
        }
    }

    int pop() {
        int x=t[1], i=1;
        t[1]=t.back();
        t.pop_back();
        while (1) {
            int j=i;
            if (2*i<t.size() && t[2*i]<t[j]) j=2*i;
            if (2*i+1<t.size() && t[2*i+1]<t[j]) j=2*i+1;
            if (i==j) break;
            swap(t[i],t[j]);
            i=j;
        }
        return x;
    }
};

int main() {
    default_random_engine rnd(123);
    BinaryHeap h;
    //vector<int> s = {6,1,8,2,3,9,0,1,2,3};
    vector<int> s;
    int n=1'000'000;
    for (int i=0;i<n;i++)  s.push_back(rnd()%n);
    for (int x : s) h.push(x);
    vector<int> u;
    for (int i=0;i<n;i++) {
        u.push_back(h.pop());
    }
    //izpisi(u);
    return 0;
}