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ę1.
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
Która oczywiście pozostanie w dalszym ciągu „logarytmiczna" - cudów bowiem w informatyce nie ma!
Wyszukiwarka
Podobne podstrony:
ALG9 5,5. Sterty i kolejki priorytetowe 139 liczbę 99 (patrz etap 5). Drzewo ma już 5-clcmentów, za
ALG3 5.5. Sterty i kolejki priorytetowe 143 Wystarczy bowiem dowolną tablicę do posortowania wpierw
ALG7 137 5.5. Sterty i kolejki priorytetowe Jednym z najłatwiejszych sposobów realizacji kolejek pr
ALG1 i 2.10. Rozwiązania i wskazówki do zadań 51Zad. 2-3 Program nie należy do zbyt skomplikowanych
ALG2 172 Rozdział 6. Derekursywacja Wzmiankowany powyżej „tajemniczy sposób” nie powinien stanowić
6 (1596) 104 Aplikacje w Delphi. PrzykładyRozwiązanie Treść procedury obsługi przycisku wykonującego
4sol 7.5. KOLEJKI PRIORYTETOWE rżenia pozostają kopcami, ale nowy korzeń może naruszać własność kopc
Kolejki i priorytety Procesy oczekujące na zwolnienie procesora mogą mieć różną ważność.
ET1 9.1. Istota jakości usług 141 wymagań klienta, trudne do pomiaru odczucia odbiorcy mające na ce
84328 ZF Bień1 Analiza progu zysku 141 produkcji nowego wyrobu, które wymagało zainstalowania nowyc
ALG1 Przedmowa 11 Początkującym zalecane jest trzymanie się porządku narzuconego przez układ rozdzi
ALG1 1.2. Jak to się niedawno odbyło, czyli. 211.2. Jak to się niedawno odbyło, czyli o tym kto „wy
ALG1 2.2. Ilustracja pojęcia rekurencji 31 od psychologii zachowań dziecka chwyciłby się za głowę z
ALG1 2.B. Typy programów rekurencyjnych 41 if (x==0) return 1; else return x*silnial !x-l); t Nie j
ALG1 3.2. Przykład 1: Jeszcze raz funkcja silnia... 61 W obliczeniach wykonywanych przez programist
ALG1 3.7. Analiza programów rekurencyjnych 71 Cały ten bagaż wzorów był naprawdę niezbędny! Dla zil
ALG1 Rozdział 4Algorytmy sortowania Tematem tego rozdziału będzie opis kilku bardziej znanych metod
więcej podobnych podstron