Sa presupunem ca vrem sa eliminam nodul de valoare 9, aducand in locul lui nodul de valoare X. Insa X poate fi orice numar mai mic sau egal cu 18. Spre exemplu, X poate fi 16, caz in care va trebui urcat deasupra nodului de valoare 10, sau poate fi 1, caz in care va trebui cernut pana la nivelul frunzelor. Deoarece caderea si urcarea se pot face pe cel mult $(log N)$ nivele, rezulta o complexitate a procedeului de $O(log N)$.
==code(c) |

void Cut(Heap H, int N, int K) {
    H[K] = H[N--];

void cut(Heap H, int& N, int K) {
    H[K] = H[N];
    --N;

    if ((K>1) && (H[K] > H[K>>1]))

    if ((K > 1) && (H[K] > H[father(K)])) {

        percolate(H, N, K);

    else sift(H, N, K)

    } else {
        sift(H, N, K);
    }

}
==

Acum, ca am stabilit toate aceste lucruri, ideea algoritmului de sortare vine de la sine. Incepem prin a construi un heap. Apoi extragem maximul (adica varful heap-ului) si refacem heap-ul. Cele doua operatii luate la un loc dureaza $O(1)+O(log N) = O(log N)$. Apoi extragem din nou maximul, (care va fi al doilea element ca marime din vector) si refacem din nou heap-ul. Din nou, complexitatea operatiei compuse este $O(log N)$. Daca facem acest lucru de $N$ ori, vom obtine vectorul sortat intr-o complexitate de $O(N log N)$.

Partea cea mai frumoasa a acestui algoritm, la prima vedere destul de mare consumator de memorie, este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are $N$ elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica $H[N]$. Dupa aceasta operatie, heap-ul va avea $N-1$ noduri, al $N$-lea ramanand liber. Ce alt loc mai inspirat decat acest al $N$-lea nod ne-am putea dori pentru a stoca maximul ? Practic, am interschimbat radacina, adica pe $H[1]$ cu $H[N]$. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.

Partea cea mai frumoasa a acestui algoritm, la prima vedere destul de mare consumator de memorie, este ca el nu foloseste deloc memorie suplimentara. Iata explicatia: cand heap-ul are $N$ elemente, vom extrage maximul si il vom tine minte undeva in memorie. Pe de alta parte, in locul maximului (adica in radacina arborelui) trebuie adus ultimul element al vectorului, adica $H[N]$. Dupa aceasta operatie, heap-ul va avea $N-1$ noduri, al $N$-lea ramanand liber. Ce alt loc mai inspirat decat acest al $N$-lea nod ne-am putea dori pentru a stoca maximul? Practic, am interschimbat radacina, adica pe $H[1]$ cu $H[N]$. Acelasi lucru se face la fiecare pas, tinand cont de micsorarea permanenta a heap-ului.

==code(c) |

void HeapSort(Heap H, int N) {
    int i;

void heap_sort(Heap H, int N) {
    build_heap(H, N);

    /* Construieste heap-ul */
    for (i=N>>1; i; sift(H, N, i--)) ;
    /* Sorteaza vectorul */
    for (i=N; i>=2;) {
        G[1] = (G[1]^G[i]) ^ (G[i]=G[1]);
        sift(H, --i, 1);

    // Sorteaza vectorul.
    for (int i = N; i >= 2; --i) {
        swap(H[1], H[i]);
        sift(H, i, 1);

    }
}
==