În consecinţă, treap-ul este un arbore binar de căutare pentru chei şi un max-heap pentru priorităţi.

În continuare, vom presupune, pentru uşurinţă, că toate cheile din treap-ul $T$ sunt distincte. Cazul în care avem nevoie să inserăm şi valori ce se repetă se va trata cu uşurinţă după ce acest articol va fi înţeles.

În continuare, vom presupune că toate cheile şi priorităţile din Treap-ul $T$ sunt distincte. În practică, presupunerea aceasta are un impact neglijabil.

Astfel, din moment ce $T$ este un heap, nodul $v$ cu prioritatea cea mai mare trebuie să fie rădăcina. Cum este şi un arbore binar de căutare, orice nod $u$ cu $cheie(u) < cheie(v)$ se găseşte în subarborele stâng al lui $v$, şi orice nod $w$ cu $cheie(w) > cheie(v)$ se găseşte în subarborele drept.

Este important să reţinem că un Treap este determinat în mod unic de chei şi de priorităţi. Prin inducţie se demonstrează că Treapul este arborele binar obţinut prin inserarea cheilor în ordinea descrescătoare a priorităţilor. Algoritmul de inserare este cel obişnuit pentru arborii de căutare. Astfel, cum fiecare set de priorităţi asociat nodurilor va aranja arborele într-un singur mod, probabilitatea ca arborele să fie echilibrat este rezonabil de mare, fapt datorat numărului mic al arborilor rău echilibraţi în comparaţie cu cei echilibraţi.
 

h2. Avantaje
Heapurile şi Arborii Binari de Căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, e suficient să fie înţeles invariantul, după care implementarea unui treap se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca Arbori Roşu-Negrii trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizate o mulţime de cazuri, pe când la Treapuri facem doar câte o rotaţie stânga sau o rotaţie dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că Arborii Roşu-Negrii sau AVL au demonstraţia că merg în $O(log N)$ şi sunt exemple didactice, dar Treapurile, deşi cu o demonstraţie mai grea, sunt mult mai uşori de implementat şi poate şi puţin mai rapizi ca arborii AVL.

}
==

Se observă că algoritmul poate fi scris şi iterativ, lucru care este indicat.

Se observă că algoritmul poate fi scris şi iterativ, lucru ce este recomandat.

h3. Inserare

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate şi îl vom insera conform algoritmului standard de inserare într-un arbore binar la baza arborelui. 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 $z$ are prioritate mai mare decât părintele său, se execută o $rotaţie$ în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, timp în care invariantul arborilor de căutare este menţinut. Timpul de inserare a 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. Se poate spune că timpul de inserare al lui $z$ este de două ori timpul necesar pentru căutarea cheii, $key(z)$.
 
Cu cât generatorul de numere pseudoaleatoare distribuie uniform priorităţi, astfel încât să nu existe două noduri cu aceeaşi prioritate, cu atât arborele este mai bine balansat.

În cadrul operaţiei de inserare vom atribui unui nod nou o prioritate şi îl vom insera, conform algoritmului standard de inserare într-un arbore binar, la baza arborelui. 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 $z$ are prioritate mai mare decât părintele său, se execută o $rotaţie$ în $z$, o operaţie locală care scade nivelul lui $z$ cu $1$ şi creşte nivelul părintelui lui $z$ cu $1$, timp în care invariantul arborilor de căutare este menţinut. Timpul de inserare a 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.

h3. Ştergere

Operaţia de ştergere, după eliminarea unui nod, va reconstrui arborele astfel încât cei doi invarianţi să fie menţinuţi. Cum fiecare set de priorităţi asociat nodurilor va reprezenta arborele într-un singur mod şi numai într-unul singur, probabilitatea ca arborele să fie echilibrat este rezonabil de mare. Acest lucru se datorează faptului că arborii rău echilibraţi sunt puţini comparativ cu cei echilibraţi.

Operaţia de ştergere, după eliminarea unui nod, va reconstrui arborele astfel încât cei doi invarianţi să fie menţinuţi.

De adăugat: insert, remove, split, join, lookup, rotleft, rotright, print, balance, meld {$O(mlog(n/m))$} - unirea a două treapuri T1 şi T2 fără nicio relaţie de ordine între ele, difference $O(mlog(n/m))$ - din T1 şi T2 rezultă un T care conţine cheile din T1 care nu sunt în T2, interpretarea geometrică, explicarea rotaţiilor (cum şi de ce se menţin invarianţii).