Kopiec - szybkość działania

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
    }
}

A musi to być kopiec bez kluczy? Jest wiele innych możliwości, ja np wybrałbym implementację drzewa rozchylanego (splay tree) i zamiast usuwać element, ustawiałbym mu flagę, oznaczającą że jest usunięty.

Za winowajcę na pierwszym miejscu brałbym strumienie z C++, tzn iostream. Użyj cstdio zamiast iostream.

Edit:
Aj sorry nie doczytałem. W sumie mój pomysł skomplikowałby sprawę znacznie i mógłby być gorszy niż zwykły kopiec.

Ogólnie to z tym printfem to bym nie przesadzał, strumienie nie są aż tak wolne, żeby nie dało się jakiegokolwiek zadania ze spoja nimi rozwiązać (na moim kompie cout jest półtora razy wolniejszy niż printf, co nie jest dużą różnicą). Problem jest z endl, dlatego, że endl nie znaczy znaku końca linii, tylko znaczy koniec linii i flush (bezwzględnie wyślij w danym momencie wszystko na wyjście). Jako, że normalnie wyjście jest buforowane, to wykonywanie tej operacji może spowolnić to twój program w dużym stopniu, ja bym spróbował najpierw zamienić endl na '\n'.

//edit Jak przeczytałem okazało się, że kiedyś iostream był zdecydowanie wolniejszy. Teraz sprawdziłem jeszcze cin vs scanf i okazało się, że cin jest szybszy w czytaniu charów (za pomocą operatora >> i z -O2 oraz z ustawioną opcją ios_base::sync_with_stdio na false). G++ 4.4.5, Debian stable, x86-32.

Dzięki za odpowiedzi, ale okazało się , że termin minął i już nie mogę sprawdzić nowej wersji, no trudno, ale będe pamiętał na przyszłość ;) Tak dla jasności, nie chodzi tu o problem złożoności operacji? To znaczy nie wykonuję tu niepotrzebnych operacji, które sprawiają, że z n, robi się 2*n?

Złożoność wydaje się być OK. Przynajmniej nie mam pomysłu jak wyciągnąć lepszą ze zwykłego kopca binarnego. Na twoim miejscu spróbowałbym takich optymalizacji:

1. Wyrzucenie zmiennej bigger. Generalnie jest ona tam zupełnie niepotrzebna.
2. Usuwałbym elementy hurtowo, tzn rekurencyjnie schodziłbym do najniższych węzłów, które są równe korzeniowi. Wtedy dopiero bym usuwał węzeł. Zysk jest taki, że odpada ci wtedy porównanie heap[*] != heap[index] w procedurze go_down. Porównanie to byłoby właśnie przeniesione do tej funkcji, o której mówiłem we wcześniejszym zdaniu.

Poza tym masz błąd - sprawdzasz zakresy po porównaniu elementów w ifie. Powinieneś to robić przed. No i nie wykorzystujesz w tych miejscach zmiennych left i right. Masz 2*index <= elements. Możesz to zamienić na left <= elements.

Z innych pomysłów to np oprócz kopca z wartościami mógłbyś trzymać mapę (wartość => ilość wystąpień). Dzięki temu nie miałbyś powtarzających się wartości w kopcu. Nie wiem tylko czy to by przyniosło jakiś wzrost wydajności. Na pewno jeśli byłoby dużo powtórzeń to tak, ale w przypadku losowych liczb mogłoby to spowolnić działanie algorytmu.