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

Rys. 5-20.

Poprawie wstawianie. nowego elementu do sterty.

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.