Witam, mam problem z kopcem binarnym napisanym w strukturze. Problem polega na tym, że przy niektórych problemach algorytmicznych kopiec robi błędy(te same algorytmy dla kolejki priorytetowej w STL działają bezbłędnie)
O pomoc zwracam się po to żeby ktoś pomógł odszukać mi błędy w tej implementacji i ewentualnie podał jakieś wskazówki co do jej poprawy.
template <typename T, typename CMP>
struct PQ
{
int n;
vector<T> pq;
CMP compare;
void restore(int i) //przywraca właściwość kopca
{
int left = 2*i;
int right = 2*i + 1;
int max = i;
if(left <= n && compare(pq[max],pq[left]))
max = left;
if(right <= n && compare(pq[max],pq[right]))
max = right;
if(max > i)
{
swap(pq[i], pq[max]);
restore(max);
}
}
PQ(int s) : n(0), pq(s+1) //konstruktor
{
}
T top() //zwraca element z najwyższym priorytetem
{
return pq[1];
}
void push(T e)//dodaje element typu T do kolejki
{
n++;
pq[n] = e;
int w = n;
while(w > 1 && compare(pq[w/2],pq[w])) //uzywa komparatora do porównywania wartosci
{
swap(pq[w], pq[w/2]);//jesli ojciec jest mniejszy od potomka zamien je
w /= 2;
}
}
bool isEmpty() //sprawdza czy kopiec jest pusty
{
if(n == 0)
return true;
else
return false;
}
int size()//zwraca rozmiar
{
return n;
}
void pop()//usuwa element z kopca
{
if(n == 0)//jesli kopiec pusty wyjdz z funkcji
return;
pq[1] = pq[n];//wrzuc element ostatni na szczyt
n--;//zmniejsz rozmiar o 1
restore(1);//zacznij przywracac wlasciwosc kopca
}
};