h2(#avantaje). Avantaje

Structurile de date de heap şi de arbori binari de căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, este suficient să fie înţeleşi cei doi invarianţi, după care implementarea se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arborii Roşu-Negru$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizată o multitudine de cazuri, pe când la treapuri facem doar câte o rotaţie stânga sau dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că se preferă ca exemple didactice $Arborii Roşu-Negru$ sau cei $AVL$ care au o demonstraţie accesibilă că limita celei mai lente operaţii este $O(log N)$. Dar treapurile, deşi cu o demonstraţie mai grea pentru limita de $O(log N)$, ce implică probabilităţi, sunt mult mai uşor de implementat, iar în practică, cu siguranţă este greu de decis care sunt mai rapizi. Sunt, deci, o opţiune demnă de luat în seamă. Pe de altă parte, treapurile suportă şi alte două operaţii pe care nu le putem face cu $Arborii Roşu-Negru$ sau cu arborii $AVL$. Aceste operaţii sunt '$join$':treapuri#join şi '$split$':treapuri#split.

Structurile de date de heap şi de arbori binari de căutare sunt uşor de implementat şi de înţeles, iar treapurile sunt o combinaţie a acestor două concepte. Astfel, este suficient să fie înţeleşi cei doi invarianţi, după care implementarea se poate face cu uşurinţă în 20 de minute, fără antrenament. De obicei, la structuri ca $Arborii Roşu-Negru$ trebuie folosite serii de rotaţii stânga şi dreapta complexe şi analizată o multitudine de cazuri, pe când la treapuri facem doar câte o rotaţie stânga sau dreapta la fiecare pas al algoritmului. Ei nu sunt predaţi pentru că se preferă ca exemple didactice $Arborii Roşu-Negru$ sau cei $AVL$ care au o demonstraţie accesibilă că limita celei mai lente operaţii este $O(log N)$. Dar treapurile, deşi cu o demonstraţie mai grea pentru limita de $O(log N)$, ce implică probabilităţi, sunt mult mai uşor de implementat, iar în practică este greu de decis care sunt cei mai rapizi. Sunt, deci, o opţiune demnă de luat în seamă. Pe de altă parte, treapurile suportă şi alte două operaţii pe care nu le putem face cu $Arborii Roşu-Negru$ sau cu arborii $AVL$. Aceste operaţii sunt '$join$':treapuri#join şi '$split$':treapuri#split.

h2(#operatii). Operaţii

    T *left, *right;
    T() {}
    T(int key, int priority, T* left, T* right) {

        this->key = key, this->priority = priority;

        this->key = key;
        this->priority = priority;

        this->left = left, this->right = right;
    }

} *R, *nil; // nil indică un nod 'gol'

} *R, *nil; // nil indica un nod 'gol'

void init(T* &R) {
    srand(unsigned(time(0)));