ALG0

140 Rozdział 5. Struktury danych

porządek. Czy czasem owa procedura nie jest na tyle kosztowna, że ewentualny | zysk z użycia steily nie jest już tak oczywisty? Na szczęście okazuje się, że nie. I Wszelkie algorytmy operujące na stercie wykonują się wprost proporcjonalnie do I długości drogi odwiedzanej podczas przechodzenia przez drzewo binarne repre- I zentujące stertę. Co można powiedzieć o tej długości wiedząc, że drzewo binarne 1 jest kompletne? Na przykład to, iż dowolny wierzchołek jest odległy od wierz- I chołka (korzenia) o co najwyżej log?/V węzłów! Z tego właśnie powodu algo- i rytmy „stertowe” wykonują się na ogół w czasie „logarytmicznym”. Jest to dobry I wynik decydujący często o użyciu tej, a nie innej struktury' danych.

Po tak długim wstępie warto wreszcie zaprezentować kilka linii kodu w C++, które lepiej przemówią niż przewlekłe wyjaśnienia. Definicja klasy I Sterta¹ jest następująca:

sterta.h

elass sterta

I

private: int *t;

int L;    // ilość elementów

public:

Sterta(int nMax)    // prosty konstruktor

(

t-new int!nMax+l);

L=0;

)

void wstaw(int x); int obsłuż(); void DoGoryl); void NaDol(); void pisz ();

); // koniec definicji klasy Sterta

Konstruktor klasy tworzy tablicę, w której będą zapamiętywane elementy -1[0] I jest nieużywane, stąd deklaracja tablicy o rozmiarze nMax+l, a nie nMcix (jest I to szczegół implementacyjny ukryty przed użytkownikiem).

Na początek zajmijmy się wstawieniem nowego elementu do sterty;

void Sterta::wstaw(int x)

{

t[++L)=x;

DoGory(); ł

Procedura DoGory była już wcześniej wzmiankowana: zajmuje się ona przywróceniem porządku w stercie po dołączeniu na koniec tablicy t nowego elementu.

1

Aby nie rozwlekać kodu nadmiernym generalizowaniem, podany zostanie przykład dla sterty liczb całkowitych.