ALG1

5.5. Sterty i kolejki priorytetowe 141

Treść procedury DoGory nie powinna stanowić niespodzianki. Jedyną różnicą pomiędzy wskazaną na rysunku 5-20 zamianą elementów jest... jej brak! W praktyce szybsze okazuje się przesunięcie elementów w drzewie, tak aby zrobić miejsce na „unoszony” do góry ostatni element tablicy:

void Sterta::DoGory()

(

int temp=t[L); int n=L;

while((n!-l)SS{t[n/2]<-temp))

I

t[n]=t[n/2]; n=n/2;

I

L[n]=temp;

)

Jest to być może zbędna „sztuczka” w porównaniu z oryginalnym algorytmem polegającym na systematycznym zamienianiu elementów ze sobą (w miarę potrzeby) podczas przechodzenia przez węzły drzewa, jednak pozwala ona nieco przyspieszyć procedurę¹.

Nawiązując do kolejek priorytetowych wspomnieliśmy, że są one łatwo implc-mentowalne za pomocą sterty. Wstawianie „klienta” do kolejki priorytetowej (czyli sterty) na sam jej koniec zostało zrealizowane powyżej. Jak pamiętamy pierwszym obsługiwanym „klientem” w kolejce priorytetowej był len, który miał największa wartość — ![]]. Ponieważ po usunięciu tego elementu w tablicy robi się „dziura”, ostatni element tablicy wstawiamy na miejsce korzenia, dekrementujemy L i wywołujemy procedurę NciDol, która skoryguje w odpowiedni sposób stertę, której porządek mógł zostać zaburzony :

int Sterta::obsłuż()

(

int x=t[1];

t[l]=t[L—);    // brak kontroli błędów!!!

NaDol(); return x;

>

(Czytelnik powinien samodzielnie rozbudować powyższą metodę, wzbogacając ją o elementarną kontrolę błędów).

Jak powinna działać procedura NuDuP Zmiana wartości w korzeniu mogła zaburzyć spokój zarówno w lewym, jak i prawym jego potomku. Nowy korzeń należy przy pomocy zamiany z większym z jego potomków przesiać w dót drzew a

1

Która oczywiście pozostanie w dalszym ciągu „logarytmiczna" - cudów bowiem w informatyce nie ma!