!heapuri?create4.JPG!
==code(c) |

void percolate(Heap H, int N, int K)
{ int Key;

void percolate(Heap H, int N, int K) {
    int Key;

  Key = H[K];
  while ((K>1) && (Key > H[ K>>1 ]))
    { H[K]=H[ K>>1 ];
      K>>=1;

    Key = H[K];
    while ((K>1) && (Key > H[ K>>1 ])) {
        H[K] = H[ K>>1 ];
        K >>= 1;

    }

  H[K] = Key;

    H[K] = Key;

}
==

Structura de heap
==code(c) |

void BuildHeap(Heap H, int N)
{ int i;
 
  for (i=N/2; i; sift(H, N, i--));

void BuildHeap(Heap H, int N) {
    int i;
    for (i=N/2; i; sift(H, N, i--)) ;

}
==

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--];

  if ((K>1) && (H[K] > H[K>>1]))
    percolate(H, N, K);

    if ((K>1) && (H[K] > H[K>>1]))
        percolate(H, N, K);

    else sift(H, N, K)
}
==

==code(c) |
void Insert(Heap H, int N, int Key)
{

  H[++N] = Key;
  percolate(H, N, N);

    H[++N] = Key;
    percolate(H, N, 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.
==code(c) |

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

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

  /* 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);

    /* 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);

    }
}
==