ALG9

5,5. Sterty i kolejki priorytetowe 139

liczbę 99 (patrz etap 5). Drzewo ma już 5-clcmentów, zatem nowy powędruje na miejsce nr 6 w tablicy - „pod” 26. W tym momencie jednak zostaje złamana zasada konstrukcji sterty: potomek węzła jest większy co do wartości niż sam węzeł, do którego jest on „przywieszony”! Co możemy zrobić, aby przywrócić porządek? W tym miejscu wystarczy zwyczajnie wymienić 26 i 99 miejscami, aby wszystko się lokalnie „uspokoiło”. Zauważmy, że taka lokalna zamiana przywraca porządek jedynie na aktualnie analizowanym poziomie -burząc go być może na następnym! Zatem aby w całej stercie zapanował porządek, należy proces zamieniania kontynuować w górę aż do osiągnięcia „korzenia”. (W naszym przykładzie konieczna będzie jeszcze zamiana liczb 99 i 41). Programową realizację opisanej powyżej czynności wykona procedura o nazwie DoGory. Opisaną sytuację ilustruje rysunek 5 - 20.

Teraz, gdy już wiemy CO to jest sterta i JAK się ją tworzy, pora wyjaśnić wreszcie dlaczego sterta umożliwia łatwe tworzenie kolejek priorytetowych. W §5.5. wymieniliśmy istotną cechę wyróżniającą kolejki priorytetowe od innych podobnych struktur danych: pierwszym obsługiwanym „klientem” jest

ten, który ma największą wartość (lub też w przypadku rekordów największą wartość pewnego wybranego pola). Jeśli trzymać się ciągle analogii kolejki do kasy sklepowej, to można by powiedzieć, że wszyscy ustawiają się elegancko na koniec „ogonka”, ale to kasjerka patrzy klientom w oczy i wybiera do obsługi tych najbardziej uprzywilejowanych (ewentualnie najprzystojniejszych...).

W przypadku list i zwykłych tablic problemem byłoby znalezienie właśnie tego największego elementu - należałoby w tym celu dokonać przeszukiwania, które zajmuje czas proporcjonalny do A'(wielkości tablicy lub listy). A jak to wygląda w naszym przypadku? Spójrzmy raz jeszcze na tablicę z rysunku 5 - 18 dla upewnienia się: TAK, my w ogóle nie musimy szukać największego elementu, bowiem z założenia znajduje się on w komórce tablicy o indeksie /!

Po euforii powinna jednak przyjść chwila zastanowienia: a co z wstawianiem? Elementy są co prawda zawsze dokładane na koniec, ale potem zawsze trzeba wywołać procedurę DoGory, która przywróci stercie zachwiany (ewentualnie) ⁵ Jeśli zachodzi oczywiście potrzeba.

Wyszukiwarka

Podobne podstrony:
ALG1 5.5. Sterty i kolejki priorytetowe 141 Treść procedury DoGory nie powinna stanowić niespodzian
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
ALG9 2.9. Zadania 49Zad. 2-3 Napisać funkcję, która otrzymując liczbę całkowitą dodatnią wypisze je
ALG 9 5.1. Listy jednokierunkowe 99 stawałby się on wówczas automatycznie głową listy i musiałby zos
77433 ZF Bień9 Preliminarz obrotów gotówkowych 139 Tablica 4 Preliminarz obrotów gotówkowych na okr
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ść.
lab9 Tablica VI c.d. Kwantyle rozkładu Snedecora (p = 0,99) NVl v2
ALG
9 1.1. Jak to wcześniej bywało, czyli... 19 • jest skończony (wynik algorytmu musi zostać „kiedy
ALG9 Rozdział 2Rekurencja Tematem niniejszego rozdziału jest jeden z najważniejszych mechanizmów uż
ALG9 2.5. Pułapek ciąg dalszy 39 nie będzie mógł sprawdzić: jak rzeczywisty kompilator wykona tę fu
ALG9 59 3.2. Przykład 1: Jeszcze raz funkcja silnia... Tę poszukiwaną funkcję będziemy zwać złożono
ALG9 3.9. Rozwiązania i wskazówki do zadań 79 ETAP 5 Poszukiwanie ostatecznego rozwiązania: Poszuki
ALG9 4.3. Quicksort, algorytm klasy Q(N log2N) 89 •    P wartość „osiowa” (zazwyczaj
ALG9 5,1. Listy jednokierunkowe 109 Poruszony powyżej problem był na tyle charakterystyczny dla wie
ALG9 5.1. Listy jednokierunkowe 119 wartość zwracaną przez funkcję: w normalnej sytuacji winien to
ALG9 5.3. Stos 129 angielskiego skrótu UFO: Last-In-First-Out, co w wolnym tłumaczeniu oznacza „ost

więcej podobnych podstron