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 tablicy³:

•    „wierzchołek” (czyli de facto korzeń, bo drzewo jest odwrócone)=/;

•    „lewy” potomek i-tego węzła jest „schowany” pod indeksem 2*/;

1

ujemnej. W naszych przykładach dla prostoty ograniczymy się tylko do przypadku składowania liczb całkowitych.

2

   Ang. heap - inna spoty kana polska nazwa to stóg.

3

   Zerowa komórka tablicy nie jest używana do składowania danych.