Kopiec jest strukturą oparta na drzewie, w której wartość rodzica jest zawsze większa(mniejsza) niż wartość potomków, dzięki temu korzeniem jest wartość największa (najmniejsza). Przedstawię w tym wpisie jej implementację tablicową kolejki priorytetowej opartej na kopcu i jej podstawowe funkcje tj. dodawanie do kopca i ściąganie z kopca(obsługiwanie).

Implementacja kopca, kolejki piorytetowej w C++

#include <cstdlib>
#include <iostream>

using namespace std;

int t[500];
int L=0; // ilosc elementow

// dodajemy na ostatni element i segregujemy

//przesun element do gory
void wynurzanie(int i)
{
    if(i>1)
    {
    int ojciec=i/2;
    if(t[i]>t[ojciec])
    {

    swap(t[i],t[ojciec]);
    wynurzanie(ojciec);
    }
    }
}

void zatapianie(int i)
{

if(i<=L)
{
        int l=2*i; // lewy potomek
        int p=l+1; // prawy potomek
        int wiekszy;

        if((l<=L)&&t[l]>t[i])
        wiekszy=l;
        else
        wiekszy=i;
        if((p<=L)&&t[p]>t[wiekszy])
        wiekszy=p;

        if(wiekszy!=i)
        {
         swap(t[i],t[wiekszy]);
         zatapianie(wiekszy);
         }

}

}

void usun()
{
      if(L<1)
    cout<<"Kolejka pusta"<<endl;
    else
    swap(t[1],t[L]);
    L--;
    zatapianie(1);
}

void wstaw(int x)
{
     t[++L]=x;
wynurzanie(L);
}

void wyswietl()
{
for(int i=1;i<=L;i++)
{
        cout<<t[i]<<" jest ojcem "<<t[i*2]<<" i "<< t[i*2+1]<<endl;
}
}

int main(int argc, char *argv[])
{

               wstaw(37);
    wstaw(41);
      wstaw(26);
       wstaw(14);
      wstaw(19);
       wstaw(99);
        wstaw(23);
         wstaw(17);
          wstaw(12);
           wstaw(20);
            wstaw(25);
             wstaw(42);

usun();
usun();

usun();
usun();
  wyswietl();
    system("PAUSE");
    return EXIT_SUCCESS;
}