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

    // balance() e apelat dupa un insert(), deci doar cel mult unul
    // din 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);

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

    // altfel e un duplicat; nu face nimic

    return balance(n);      // restabileste invariantul heapurilor
}

        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`

            // 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);

{
    if (n != nil)
    {

        empty(n->left);
        empty(n->right);

        empty(n->left), empty(n->right);

        delete n;
    }
    return nil;