ALG7
137
5.5. Sterty i kolejki priorytetowe
Jednym z najłatwiejszych sposobów realizacji kolejek priorytetowych jest użycie struktury danych zwanej stertą1 2. Sterta jest swego rodzaju drzewem binarnym, które ze względu na szczególne własności warto omówić osobno. (Kwestia terminologiczna: zarówno sterta, jak i kolejki priorytetowe są strukturami danych, jednakże tylko kolejka priorytetowa ma charakter czysto abstrakcyjny).
Uporządkowanie elementów wchodzących w skład sterty można zaobserwować na rysunku 5-18 przedstawiającym 72-clcmcntową stertę. Jest to również przykład tzw. kompletnego drzewa binarnego. Stosując pewne uproszczenie definicyjne można także powiedzieć, iż jest to „drzewo bez dziur”... Jeśli spojrzeć na numery przypisane węzłom drzewa, to widać, że ich kolejność definiuje pewien charakterystyczny porządek wypełniania go: pod istniejące węzły „dowieszamy” maksymalnie po dwa nowe aż do ulokowania wszystkich 72-elementów. Można to oczywiście wyrazić nieco bardziej formalnie, ale zapewniam, że zdecydowanie mniej zrozumiale.
Rys. 5 - IS.
Sterta i jej tablicowa implementacja.
|
N |
5 |
R |
6 |
F. |
7 |
3 |
|
A |
9 |
u |
10 |
0 |
11 |
F |
12 |
c |
10 11 12
|
Y |
T |
S |
N |
R |
E |
L |
A |
D |
O |
F |
C |
Liniowy porządek wypełniania drzewa automatycznie sugeruje sposób jego składowania w tablicy3:
• „wierzchołek” (czyli de facto korzeń, bo drzewo jest odwrócone)=/;
• „lewy” potomek i-tego węzła jest „schowany” pod indeksem 2*/;
ujemnej. W naszych przykładach dla prostoty ograniczymy się tylko do przypadku składowania liczb całkowitych.
Ang. heap - inna spoty kana polska nazwa to stóg.
Zerowa komórka tablicy nie jest używana do składowania danych.
Wyszukiwarka
Podobne podstrony:
ALG9 5,5. Sterty i kolejki priorytetowe 139 liczbę 99 (patrz etap 5). Drzewo ma już 5-clcmentów, za
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
Dygresja - oczekiwanie w jądrze• Jednym ze sposobów realizacji aktywnego czekania
David Kahn Krav maga7 O AUTORZE David Kahn jest jednym z głównych ekspertów w dziedzinie kroco maga
8 (137) Kl^vfikaćTg*sociologiczne I ^Jednym z twórców takiej klasyfikacji jest Florian gnaniecki Wg
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ść.
DSC01928 (3) 3. tjiiślinuż.mwiśi: - wydaje siv jednym / najlatwiejs/ycli sposobów /.dobywania żywnoś
ALG7 Rozdział 1Zanim wystartujemy Zanim na dobre rozpoczniemy operowanie takimi pojęciami jak wspom
ALG7 1.5. Poprawność algorytmów 27 {warunki wstępne 1} poszukiwany-program {warunki końcowe} Możliw
ALG7 2.4. Niebezpieczeństwa rekurencji 37 return (x-10); else return MacCarthy(MacCarthy(x111}); 1
ALG7 2.9. Zadania 472.9.Zadania Wybór reprezentatywnego dla rekurencji zestawu zadań wcale nie był
ALG7 3.1. Dobre samopoczucie użytkownika programu 57 mów zostaną wprowadzone na reprezentatywnych p
ALG7 3.5. Przykład 4: Różne typy złożoności obliczeniowej 67 Koszt algorytmu oznaczmy klasycznie pr
ALG7 3.8. Zadania 77b) T(n2) e 0(«3); c) 7’(2"+l) e 0(2&qu
ALG 7 5.1. Listy jednokierunkowe 97 public: int pusta() // czy lista jest pusta? {
ALG7 5.1. Listy jednokierunkowe 107 cout « "L2 = for (i=0; i<n; 12.dorzuc2(tab2[i++])) ; 12
więcej podobnych podstron