Pentru o rotaţie sunt necesare doar câteva operaţii cu pointeri.

== code(cpp) |
void rotleft(T* &n)
{
    T *t = n->left;
    n->left = t->right, t->right = n;
    n = t;
}
 
void rotright(T* &n)
{
    T *t = n->right;
    n->right = t->left, t->left = n;
    n = t;
}
 
void balance(T* &n)
{
    if (n->left->priority > n->priority)
        rotleft(n);
    else if (n->right->priority > n->priority)
        rotright(n);
}
==
 

Complexitate: $O(1)$.
h3(#inserare). Inserare

Cheile formează un arbore de căutare, dar priorităţile pot să nu mai formeze un heap. Pentru a redobândi această proprietate, cât timp nodul de inserat, are prioritatea mai mare decât a părintelui său, se va executa o '$rotaţie$':treapuri#rotatii în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, şi care menţine invariantul arborilor de căutare. Timpul de inserare al lui $z$ este proporţional cu adâncimea lui înainte de rotaţii - trebuie să coborâm după care să urcăm înapoi efectuând rotaţiile necesare.

== code(cpp) |
void insert(T* &n, int key)
{
    if (n == nil)
    {
        n = new T();
        n->key = key, n->priority = rand() + 1,
                    n->left = n->right = nil;
        return;
    }
    if (key < n->key)
        insert(n->left, key);
    else if (key > n->key)
        insert(n->right, key);
 
    balance(n);
}
==
 

Complexitate: $O(log N)$.
h3(#stergere). Ştergere
Operaţia de ştergere este inversul operaţiei de inserare. Scopul este să aducem acest nod, fie el $z$, în poziţia unei frunze pentru a-l şterge. Astfel, pentru a menţine cei doi invarianţi (făcând excepţie de $z$) vom alege fiul cu prioritatea mai mare şi îl vom '$roti$':treapuri#rotatii în locul lui $z$, cât timp acesta nu este frunză. Atunci când $z$ devine frunză îl vom şterge.

== code(cpp) |
void erase(T* &n, int key)
{
    if (n == nil)   return ;
 
    if (key < n->key)
        erase(n->left, key);
    else if (key > n->key)
        erase(n->right, key);
    else {
        (n->left->priority > n->right->priority) ? rotleft(n) : rotright(n);
        if (n != nil)
            erase(n, key);
        else {
            delete n->left;
            n->left = NULL;
        }
    }
}
==
 

Complexitate: $O(log N)$.
h3(#split). Split