T* balance(T *n)    // restabileste invariantul heapurilor
{

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

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

    if (n->left->priority > n->priority)
        return rotleft(n);

    return n;       // altfel nu face nimic
}

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

T* insert(T *n, int key)

{

    if (n == nil)

    if (n == nil)   // am gasit locul in care trebuie inserata cheia key

    {

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

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

    else if (key > n->key)
        n->right = insert(n->right, key);
    // altfel e un duplicat; nu face nimic

 
    return balance(n);

    return balance(n);      // restabileste invariantul heapurilor

}
T* erase(T *n, int key)

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

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

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

            n = (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
            if (n != nil)   // continua
                n = erase(n, key);