Napisałem własną implementację kopca, tylko jest jeden problem, przekracza mi limit czasowy w jednym teście na SPOJu ale nie wiem jak to ulepszyć, co jest zbędne etc. Możę ktoś coś poradzić? Generalnie program ma sprawdzać czy wprowadzona liczba jest równa obecnemu korzeniowi, jeżeli tak to ma usuwać wszystkie elementy o tej wartości.
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
void heapify(int number, int *heap); //przwracanie wlasnosci kopca
void add_element(int value, int *heap, int &elements);
void go_down(int index,int *heap, int elements);
void remove(int *heap, int &elements);
int main()
{
int elements = 0;
int storage = 0; //ile bêdzie elementów
int number;
cin >> storage;
int *heap = new int [storage];
while(storage--)
{
cin >> number;
if(number == heap[1] && elements > 0)
{
while(number == heap[1] && elements > 0)
{
remove(heap, elements);
}
cout << number << endl;
}
else
{
add_element(number, heap, elements);
}
}
delete heap;
}
void heapify(int number, int *heap) //przywracanie w³asnoœci kopca
{
if(number > 1) //je¿eli nie ma tylko korzenia w kopcu
{
int father = number/2; //index ojca
if(heap[number] > heap[father]) //je¿eli dziecko ma wiêksza wartoœæ
{
swap(heap[number], heap[father]); //zamieniamy i sprawdzamy czyl nie trzeba znowu zamieniæ
heapify(father, heap);
}
}
}
void add_element(int value, int *heap, int &elements)
{
heap[++elements] = value;
heapify(elements, heap);
}
void go_down(int index,int *heap, int elements)
{
if(index <= elements) //maxymalny zasięg potomków
{
int left = 2*index;
int right = 2*index + 1;
int bigger = 0;
//sprawdzam, który potomek ma większą wartość, bo z nim będe teraz swapował
if(heap[left] >= heap[right] && heap[left] > heap[index] && 2*index <= elements)
{
bigger = left;
}
else if(heap[right] > heap[left] && heap[right] > heap[index] && (2*index + 1) <= elements)
bigger = right;
else
bigger = 0;
if(bigger == left) //je¿eli ojciec mniejszy od lewego potomka
{
swap(heap[index], heap[left]);
go_down(left, heap, elements);
}
else if(bigger == right)//je¿eli ojciec mniejszy od prawego potomka
{
swap(heap[index], heap[right]);
go_down(right, heap, elements);
}
}
}
void remove(int *heap, int &elements)
{
if(elements > 0) //nie chcemy usuwaæ z pustego kopca
{
swap(heap[1], heap[elements]); //zamienaimy liϾ z korzeniem
--elements; //zmiejszamy iloœæ elementów
go_down(1, heap, elements); //musimy przywróciæ w³asnoœæ kopca je¿eli na górze znajdzie siê element mniejszy ni¿ na wierzcho³kach
}
}