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

} *R, *nil;

    T() {}
    T(int key, int priority, T* left, T* right) {
        this->key = key, this->priority = priority,
                    this->left = left, this->right = right;
    }
} *R, *nil;     // R radacina; nil arata un nod `gol`

void init(T* &R)
{

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)

void insert(T* &n, int key, int priority)

{

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

    if (n == nil) {
        n = new T(key, priority, nil, nil);

        return;
    }

    if (key < n->key)
        insert(n->left, key);

    if (key <= n->key)
        insert(n->left, key, priority);

    else if (key > n->key)

        insert(n->right, key);

        insert(n->right, key, priority);

    balance(n);
}

Costul operaţiei $split$ este egal cu costul operaţiei de '$inserare$':treapuri#inserare a lui $z$.

== code(cpp) |
void split(T* &R, T* &Ts, T* &Tg, int key) {
    insert(R, key, infinity);
    Ts = R->left, Tg = R->right;
}
==
 

Complexitate: $O(log N)$.
h3(#join). Join

Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât oricare cheie din $T{~>~}$, într-un singur super-treap. $Join$ se realizează în mod invers operaţiei de $split$ prin crearea unei rădăcini $z$, ce are ca subarbore stâng pe $T{~<~}$ iar ca subarbore drept pe $T{~>~}$, pe care o vom suprima. Dacă în treap avem noduri $w$ cu $key(w) = key(z)$ atunci acestea ar trebui să rămână.

Operaţia $join$ constă în unirea a două treapuri $T{~<~}$ şi $T{~>~}$, unde fiecare cheie din $T{~<~}$ este mai mică decât o cheie $key$ iar oricare cheie din $T{~>~}$ este mai mare decât aceeaşi cheie $key$, într-un singur super-treap. $Join$ se realizează în mod invers operaţiei de $split$ prin crearea unei rădăcini $z$ cu cheia $key$ şi prioritate oricât, ce are ca subarbore stâng pe $T{~<~}$ iar ca subarbore drept pe $T{~>~}$, pe care o vom suprima.

Costul operaţiei $join$ este egal cu costul operaţiei de '$ştergere$':treapuri#stergere a lui $z$.

== code(cpp) |
void join(T* &R, T* T1, T* T2, int key) {
    R = new T(key, 0, T1, T2);
    erase(R, R->key);
}
==
 

Complexitate: $O(log N)$.
h2(#concluzii). Concluzii