klasa kopiec konstruktor

witam
napisalem klase imitujaca dzialanie kopca:

 

class Heap
{
    public:
        Heap(int max_size)
        {
            t=new int[max_size+1];
            current_size=0;
        };

        //**********************************************
        void insert_int(int x)
        {
            t[++current_size]=x;
            GoUp();
        }
        //**********************************************
        void GoUp()
        {
            int temp=t[current_size];
            int n=current_size;

            while((n!=1) && (t[n/2]<=temp))
            {
                t[n]=t[n/2];
                n=n/2;
            }
            t[n]=temp;
        }
        //**********************************************
        int get_first()
        {
            int x=t[1];
            t[1]=t[current_size--];

            GoDown();
            return x;
        }
        //**********************************************
        void GoDown()
        {
            int i=1;
            while(true)
            {
                int p=2*i;
                if(p>current_size)
                    break;
                if(p+1<=current_size)
                    if(t[p]<t[p+1])
                        p++;
                if(t[i]>=t[p])
                    break;

                int temp=t[p];
                t[p]=t[i];
                t[i]=temp;

                i=p;
            }
        }


    private:
        int *t;
        int current_size;
};

otóż gdy w funkcji main napisze:

 
Heap S(13);

to program po uruchomienu mi sie wywala.
moglby ktos pomoc lub wskazac ewentualne bledy jakie popelnilem?

bede wdzieczny za kazda pomoc

E tam, nieprawda: http://ideone.com/QB5Q7F

• w konstruktorze Ci się nie wywala
• nie zapisujesz nigdzie max_size w związku z czym nie sprawdzasz przepełnienia kopca w insert_int
• nie napisałeś destruktora

znalazlem blad w swoim programie (w main zle rzutowalem i sie wywalal program-jak zwykle - wykladam sie na najprostszych rzeczach i potem sam sie smieje ze swoich bledow) i teraz wszystko dziala jak nalezy.
Ale i tak dziekuje ze zechciales sprawdzic moj kod ;)
temat do zamkniecia

Tak w życiu, kiedy warto skorzystać z kopca? Ja wiem, że kopiec może posortować dane, ale większośc języków ma jakieś wbudowane metody do sortowania (typu quicksort).

:-P napisał(a):

Tak w życiu, kiedy warto skorzystać z kopca?
Np. jak chcesz mieć kolejkę priorytetową.

Ja kiedyś usłyszałem takie coś. Myślę, że to fajnie obrazuje to jak w niektórych sytuacjach pomaga kopiec.

Załóżmy, że jest sobie hurtownia, która ma 4 miliardy zamówień i te 4mld się ciągle utrzymuje bo jedne zamówienia są realizowane, ale dochodzą nowe.
Każde zamówienia ma jakiś tam priorytet i to jest głównym wyznacznikiem, które zamówienie ma być wykonane następnie.
I teraz gdybyśmy mieli zamówienia trzymane w tablicy, trzeba by było ich przejrzeć 4 miliardy zanim zostanie znalezione to o najniższym priorytecie.
A jak trzymamy je w kopcu. To wystarczy wziąć zamówienie z jego wierzchołka i naprawić kopiec. Naprawienie kopca kosztuje tyle co przejrzenie 32 (zamiast czterech miliardów) zamówień. 32 bo taka jest wysokość kopca przy czterech miliardach elementów.

W skrócie. Kopiec przydaje się tam gdzie musisz często wybierać najmniejszy lub największy element.

zgadzam sie ze stryku

stryku. Jezeli bedziesz miec 4 miliardy zamowien nikt normalny nie bedzie trzymal tego w tablicy tylko w bazie danych (zeby miec chociazby historie zamowienia).
Mozesz sobie z bazy danych zrobic SQLa z sortowaniem i miec rekordow tyle ile Ci potrzeba.

Takze teoretycznie masz racje, praktycznie nie masz racji bo nikt normalny nie bedzie uzywal takiego rozwiazania.

fasadin napisał(a):

Takze teoretycznie masz racje, praktycznie nie masz racji bo nikt normalny nie bedzie uzywal takiego rozwiazania.

I tak i nie. SQL przy dużych zbiorach też jest do ... powieszenia na ścianie.

Z drugiej strony nikt normalny nie będzie trzymał 4 mld danych w pamięci, chyba że akurat to się będzie opłacało. Ale to raczej w zastosowaniach naukowych niż biznesowych.

BTW, kopiec można też stosować do sortowania (heapsort), dla mnie łatwiejsze do zapamiętania niż quick sort.

@fasadin Ale ja nie mówiłem, że ktoś tak robi :p Tak jak powiedziałeś, chciałem pokazać w teorii przewagę kopca. Normalne, że nie trzymamy tak wielkiej ilości danych w RAMie. Ale można też przecież mieć kopiec z danymi w pliku ;) I bazy danych tak robią. Tylko, że nie używają kopca tylko B-drzewa, żeby było jeszcze mniej odczytów. I zamiast 32 odczytów mamy 5 albo mniej