BAL - ćwiczenia nr 5

30 listopada 2011

Algorytmy na drzewach binarnych

Algorytm sortowania oparty na wykorzystaniu drzewa binarnego typu
kopiec.

Algorithm 1 Algorytm sortowania przez kopcowanie
Opis słowny

1. START

2. Wywołuj procedurę wstawiania elementów tablicy do kopca, aż do wyko-

rzystania wszystkich elementów.

3. Wywołuj procedurę usuwania korzenia i przywracania warunku kopca, aż

do momentu rozebrania całego kopca.

4. Tablica złożona z usuwanych kolejno korzeni zawiera posortowane ele-

menty.

5. STOP

Algorithm 2 Sortowanie tablic metodą kopcowania

WE: T (N ) - tablica do posortowania

wywołaj procedurę utwórz_kopiec dla tablicy T (N )

powtarzaj od m = N w dół do m = 2

zamień(T

m

, T

1

)

wywołaj procedurę przywróć_kopiec dla tablicy T (m − 1)

zakończ iterację

WY: T (N ) (tablica T (N ) jest posortowana )

1

Algorithm 3 Tworzenie kopca z zadanych elementów tablicy
procedura utwórz_kopiec

WE: T (N ) (tablica do “zakopcowania”)

powtarzaj od m = 2 do N

rodz ← [m/2]

// indeks rodz wskazuje na rodzica m-tego elementu

dopóki rodz > 0 oraz T

rodz

< T

m

powtarzaj

zamień(T

rodz

, T

m

)

m ← [m/2]

// problem wędruje piętro wyżej

rodz ← [m/2]

// rodzicielstwo również “awansuje”

zakończ iterację

zakończ iterację

zakończ procedurę

Po zakończeniu procedury T (N ) ma strukturę kopca.

Algorithm 4 Przywracanie warunku kopca
procedura przywróć_kopiec

WE: T (N ) (tablica w której zaburzono warunek kopca)

i ← 2
dopóki od i ≤ N powtarzaj

jeśli i < N oraz T

i

< T

i+1

i ← i + 1 // wybieramy potomka o wyższej wartości

rodz ← [i/2] // element o indeksie rodz jest rodzicem i -tego elementu kopca

jeśli T

rodz

≥ T

i

przerwij procedurę

// bo warunek kopca jest spełniony

w p.p.

zamień(T

i

,T

rodz

)

i ← i · 2

// schodzimy do niższego poziomu drzewa

zakończ iterację

zakończ procedurę

Po zakończeniu procedury w T (N ) przywrócono strukturę kopca.

2