int key;
    int priority;
    T *left, *right;

} *R, *nil;     // R radacina; nil arata un nod `gol`

} *R, *nil;

void init(T* &R)
{
    srand(unsigned(time(0)));

    R = nil = new T();
    nil->key = nil->priority = 0,
        nil->left = nil->right = NULL;
}

void rotleft(T* &n)    // roteste fiul stang

void rotleft(T* &n)

{
    T *t = n->left;
    n->left = t->right, t->right = n;

    n = t;             // noua radacina

    n = t;

}

void rotright(T* &n)   // roteste fiul drept

void rotright(T* &n)

{
    T *t = n->right;
    n->right = t->left, t->left = n;

    n = t;             // noua radacina

    n = t;

}

void balance(T* &n)    // restabileste invariantul heapurilor

void balance(T* &n)

{

    // balance() e apelat dupa un insert(), astfel doar cel mult unul din cei doi fii nu respecta invariantul heapurilor

    if (n->left->priority > n->priority)
        rotleft(n);
    else if (n->right->priority > n->priority)
        rotright(n);

    // altfel nu face nimic

}

void insert(T* &n, int key)    // insereaza cheia 'key'

void insert(T* &n, int key)

{
    if (n == nil)
    {

        // adaugam cheia 'key' prin crearea unui nou nod

        n = new T();
        n->key = key, n->priority = rand() + 1,
                    n->left = n->right = nil;

        insert(n->left, key);
    else if (key > n->key)
        insert(n->right, key);

    // altfel e un duplicat; nu face nimic

    balance(n);
}

        erase(n->left, key);
    else if (key > n->key)
        erase(n->right, key);

    else {    // am gasit cheia
        // pune fiul cu prioritatea cea mai mare ca radacina in locul lui 'n'

    else {

        (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);

        if (n != nil)   // continua

        if (n != nil)

            erase(n, key);
        else {
            delete n->left;

    }
}

void _empty(T* &n)
{
    if (n != nil)
    {
        _empty(n->left), _empty(n->right);
        delete n;
    }
}
 
void empty(T* &R)
{
    _empty(R), R = nil;
}
 
void print(T *n)
{
    if (n != nil)
    {
        print(n->left);
        printf("%d ", n->key);
        print(n->right);
    }
}
 
int main(void)
{
    init(R);
    // 1 s pentru a insera un milion de numere
    for (int i = 1 << 20; i >= 1; -- i)
        insert(R, i);
    // 0.5 s pentru a sterge un milion de numere
    for (int i = 1; i <= 1 << 20; ++ i) if (i < 11 || i > 25)
        erase(R, i);
    print(R);
    empty(R);
    print(R);
    return 0;
}
 

==