Alg11.pdf
(
429 KB
)
Pobierz
119
120
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
11. ZŁOśONE STRUKTURY DANYCH
11.1. Drzewa dwumianowe
(binomial tree)
Jest to drzewo uporządkowane
B
h
o wysokości
h
składające
się z
dwóch
drzew
B
h1
razem powiązanych.
Korzeń jednego
drzewa
jest
skrajnie
lewym
synem drugiego.
Własności: 1.
drzewo
B
h
ma 2*2
h1
= 2
h
węzłów (
h
–wysokość)
2. na głębokości
i
znajduje się
C(k, i)
węzłów, gdzie i = 0,1,…h.
3. stopień korzenia wynosi
h
i jest większy od stopnia kaŜdego innego węzła.
4. jeŜeli synów korzenia ponumerujemy kolejno od lewej do prawej: h1, h2,…0 to
syn o numerze
i
jest korzeniem poddrzewa
B
i
.
Katedra Aparatów Elektrycznych
Alg11
Algorytmy i Struktury Danych – wykład/1st
Algorytmy i Struktury Danych – wykład/1st
Dr J. Dokimuk
11.2. Kopiec dwumianowy
Kopiec dwumianowy H
jest zbiorem
drzew dwumianowych.
Własności kopca dwumianowego:
1.
KaŜde drzewo
dwumianowe w kopcu
H
jest
uporządkowane kopcowo,
czyli
klucz ojca
jest
mniejszy
niŜ klucz węzła syna.
Klucz w korzeniach
drzew
kopca jest
najmniejszym kluczem w drzewie.
2. Dla kaŜdego
r ≥ 0
istnieje w
kopcu
dwumianowym
co
najwyŜej
jedno
drzewo dwumianowe,
którego korzeń ma stopień równy
r
.
Kopiec dwumianowy składa się co najwyŜej z
lg
(
n
)
+
1
drzew dwumianowych.
Własności pola sibling:
jeŜeli
x
jest korzeniem, to
sibling
[
x
] wskazuje na
następny korzeń na
liście korzeni
.
jeśli
x
jest ostatnim korzeniem na
liście korzeni
to
sibling
[
x
] = NULL.
Dowolny kopiec
H
dostępny jest przez wskaźnik
head
[H] do pierwszego korzenia na liście korzeni
H
.
Kopiec nie zawiera elementów to
head
[H] = NULL.
Operacje na kopcach dwumianowych:
Make_B_Heap
()
-tworzy nowy, pusty kopiec
Insert_B_Heap
(
H
,
x
) -wstawia węzeł
x
o kluczu
key
do kopca
H
Min_B_Heap
(
H
)
zwraca wskaźnik do węzła w z minimalnym kluczem
DelMin_B_Heap
(H)
-zwraca wskaźnik do węzła z minimalnym
kluczem i węzeł usuwa z
H
Union_B_Heap
(
H1
,
H2
) -tworzy nowy kopiec ze węzłami
H1
i
H2
Dec_B_Heap
(
H, x,
key
)
-nadaje kluczowi w węźle
x
wartość
key
Del_B_Heap
(
H
,
x
) -usuwa węzeł
x
z
H
11.2.1. Tworzenie nowego kopca dwumianowego
Funkcja
Make_B_Heap
() buduje pusty kopiec dwumianowy, przydzielając
pamięć obiektowi, którego adres zwraca.
Dla zwracanego obiektu
head
[H] = NULL.
Czas wykonania operacji jest stały O(1).
11.2.2. Szukanie minimalnego klucza
Drzewo kopca dwumianowego uporządkowane są
wg minimum, zatem minimalny klucz znajduje się
w korzeniu
któregoś
drzewa.
Min_B_Heap
(
H
)
sprawdza kolejno wszystkie
korzenie
,
pamiętając bieŜące minimum w zmiennej
min
, a
wskaźnik do węzła z tym
min
imum w zmiennej
y
.
Funkcja zwraca wskaźnik do węzła z minimalnym
kluczem w kopcu dwumianowym
H
.
ZłoŜoność
B
h
B
0
B
h1
ukorzenione
poddrzewo
5
10
15
10
12
B
h1
21
19
33
16
25
Rys. 11.3. Przykład kopca dwumianowego
Rys. 11.4. Reprezentacja kopca dwumianowego
Rys. 11.1. Przykłady drzew dwumianowych.
Z metodyki montaŜu dwóch drzew
B
h1
w jedno
B
h
wynika, Ŝe maksymalna głębokość węzła w
B
h
jest o jeden większa od maksymalnej w
B
h1
.
Maksymalny stopień węzła w drzewie dwumianowym wynosi
lg
(
n
).
p[x]
key[x]
degree
key
degree
degree[
x
]
Struktura węzła:
1. wskaźnik do Ojca
p
[x],
2. klucz
key
[x],
3. stopień
degree[x]
–liczba
synów
,
4a.
wskaźnik
do skrajnego
lewego
syna
child[x]
,
4b. wskaźnik do brata z prawej strony
sibling[x]
.
typedef
nodeBinT
struct {
nodeBinT
*parent;
key
x
;
int
degree
;
nodeBinT
*
child
, *sibling
;
} *
pnodeBinT
;
pnodeBinT
head
= NULL;
child
child[
x
]
sibling
sibling
sibling
[x]
2
10
12
Łączenie dwóch drzew dwumianowych
Funkcja
Link_B_Tree
(
y
,
z
)
dowiązuje drzewo
B
h1
o korzeniu w
węźle
y
do drzewa
B
h1
o
korzeniu w
węźle
z
.
Węzeł
z
staje się ojcem
i
zostaje korzeniem drzewa
B
h
Węzeł
y
zostaje nową głową
listy synów
węzła
z
.
Zasada „
na lewo syn, na prawo brat"
drzewa dwumianowego:
-
w drzewie
B
h
skrajnie lewy syn korzenia jest korzeniem drzewa
B
h1
.
r
16
Min_B_Heap
(
H
)
y
= NULL // wskaŜnik do węzła z minimum
x = head(H)
min = +inf
while
(x ≠ NULL)
do
if
(key[x] < min)
then
min
=
key
[
x
]
y
=
x
x =
sibling
[x]
//następny wezeł
return
y
z
2
2
z
y
degree
degree =
2
degree
degree =
3
1
Link_B_Tree
(
y
, z
)
p[
y
] = z
degree[z] = degree[z] +1
child[z] =
y
;
sibling
[
y
] =
child
[z]
y
z
4
1
6
0
y
1
2
3
5
2
4
6
3
5
4
6
7
8
0
obliczeniowa
wynosi
O
(
lg(n)
)
,
poniewaŜ
8
7
8
sprawdza się co najwyŜej
lg(n) +1
korzeni.
Funkcja działa w czasie stałym.
121
122
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
11.2.3. Łączenie
dwóch
kopców dwumianowych
Jest to najwaŜniejsza operacja, za pomocą której definiuje się większość pozostałych.
Funkcja
Union_B_Heap
(
H1
,
H2
)
łączy kopce dwumianowe
H
1
i
H
2
w jeden kopiec, po czym oba
kopce zostają zniszczone.
Jej działanie jest dwuetapowe.
1szy
etap:
Scalanie
listy korzeni kopców w pojedynczą listę
H
,
uporządkowaną według
stopni
.
Lista
H
moŜe zawierać
najwyŜej
dwa korzenie o
tym samym
stopniu.
2gi
etap:
Łączenie
korzenie o
tym
samym
stopniu, aŜ pozostaną tylko o róŜnych stopniach.
Funkcja działa w czasie
O
(
lg
(
n
)) gdzie n = n
H1
+ n
H2
.
Łączenie przypomina dodawania liczb binarnych, przy czym sumowaniu jedynek odpowiada
łączenie dwóch drzew dwumianowych: korzeń z mniejszym kluczem zostaje korzeniem
wynikowego drzewa ('przeniesienia'), a drugi korzeń zostaje jego skrajnie lewym synem.
Zmienne pomocnicze wskazujące na:
x
aktualnie
badany korzeń
prev_x
korzeń poprzedzający
x
next_x
korzeń następny po
x
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
Merge_B_Heap
(H1, H2):
porównuje korzenie na liście korzeni kopców
H1
i
H2
,
dodaje korzeń o mniejszym
stopniu
do listy wynikowej
H
,
usuwa dodany korzeń z listy wejściowej.
Funkcja gwarantuje, Ŝe na liście
H
dwa korzenie o tych samych stopniach są sąsiadami
ZłoŜoność obliczeniowa O(
n
h1
+
n
h2
)
JeŜeli połączone kopce okaŜą się puste funkcja
Union_B_Heap
() kończy działanie.
Algorytmy i Struktury Danych – wykład/1st
Algorytmy i Struktury Danych – wykład/1st
Union_B_Heap
(
H1, H2
)
1
H =
Make_B_Heap
()
// scalanie listy korzeni H1 I H2 w jedną listę uporządkowaną wg
stopni
2
head[H] =
Merge_B_Heap
(H1, H2)
3
Zwolnij(obiekty H1 i H2)
// ale nie listy na które wskazują
4
if
(head[H] = NULL)
then
return
H
//
połączone kopce są puste
// -----------------------------------------
2gi etap
----------------------------------------------------
6
prev_x = NULL
7
x = head[H]
//zmienne pomocnicze
8
next-x = sibling[x]
9
while
(
next-x ≠ NULL)
do
10
if
(
(degree[x] ≠ degree[next_x])
or
// badanie czy przypadek 1 lub 2
(
sibling[next_x] ≠ NULL
and
degree[sibling[next_x]] = degree[x])
)
11
then
prev_x= x; x = next_x
// obsługa przypadku 1 i 2
12
else
if
(key[x] ≤ key[next_x])
then
sibling[x] = sibling[next_x]
// przypadek 3
13
Link
_B_Tree
(next_x, x)
14
else
if
(prev_x = NULL)
//przypadek 4
15
then
head[H] = next_x
16
else
sibling[prec_x] = next_x
17
Link
_B_Tree
(x, next_x)
18
x = next_x
//aktualizacja x przed następnym obiegiem
19
next_x = sibling[x]
20
return
H
6
÷
8
ustawienie zmiennych pomocniczych.
9
÷
10
badane są
stopnie
węzłów
x
,
next_x
oraz
sibling
[
next_x
] w celu podjęcia decyzji o
ewentualnym scalaniu.
11
występuje
przypadek 1
, zatem nie ma łączenia tylko przemieszczenie wskaźników.
12
next_x
jest usuwane z listy korzeni, zaś w
13
next_x
zostaje skrajnie lewym synem
x
.
14
÷
16
węzeł
x
jest usuwany z listy korzeni. (
15
gdy
x
jest 1-szym korzeniem na liście)
17
węzeł
x
zostaje skrajnie lewym synem
next_x.
19
next_x
ma wskazywać węzeł występujący po nowym węźle (wspólne dla wszystkich przypadków).
Rys. 11.5. Łączenie dwóch kopców dwumianowych
Przypadek 1:
gdy
x
jest korzeniem drzewa
B
h1
zaś
next_x
drzewa
B
h2
, dla h2
>
h1.
tzn. degree[x] ≠ degree[next_x].
Nie
są podejmowanie Ŝadne czynności, poza przesuwaniem wskaźników.
Przypadek 2:
na liście znajdują się
3
korzenie
o
tym samym
stopniu, następuje przesunięcie
wskaźników roboczych, co jest przygotowaniem do scalenia w
następnym
kroku.
Wystąpi przy scaleniu dwóch drzew w jedno
B
h
gdy dwa następne są teŜ typy
B
h
Przypadek 3 i 4:
gdy
x
jest 1szym z
dwóch
korzeni o
tym samym
stopniu
.
Łączone są drzewa
x
i
next_x
we właściwej kolejności
(zachowanie kopcowatości).
11.2.4. Wstawianie węzła
Wstawienie węzła stanowi szczególny przypadek
Union_B_Heap
(
H1, H2
)
(łączenie z kolejką jednoelementową).
Funkcja tworzy
1
węzłowy kopiec dwumianowy
H1
w czasie
O(1)
i łączy go z
n
-węzłowym kopcem dwumianowym w czasie O(lg(n)).
Tymczasowy kopiec
H1
zostaje zniszczony.
Insert_B_Heap
(
H, x
)
H1
= Make_B_Heap()
p[x] = NULL; degree[x] = 0
child[x] = NULL
sibling[x] = NULL
head(
H1
) = x
H
=
Union_B_Heap
(
H,
H1
)
(3)
gdy
key[x] ≤ key[next_x];
next_x
jest podczepiane pod
x
.
(4)
gdy
key[x] > key[next_x];
x
jest podczepiane pod
next_x
.
123
124
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
11.2.5. Usuwanie węzła
z
minimalnym kluczem
Funkcja
DelMin_B_Heap
(
H
)
znajduje, zwraca i usuwa z listy
H
węzeł z najmniejszym kluczem.
Gdzie naleŜy szukać najmniejszego klucza ?
Następnie łączy listy synów usuniętego węzła z
H
.
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
11.2.6. Zmniejszanie wartości klucza
Funkcja
Dec_B_Heap
(
H, x,
key
)
nadaje kluczowi w węźle
x
nową wartość
key
.
Gdy
key
jest większe od bieŜącego klucza w
x
generowany jest błąd.
Wykonuje się podobnie jak poprawianie zwykłego kopca przy wstawianiu elementu:
-
Przesuwaj
zmniejszony klucz w górę
swojego
drzewa dwumianowego,
-
Zamieniaj
miejscami
(gdy trzeba)
z Ojcem aŜ odtworzony zostanie warunek kopca.
Algorytmy i Struktury Danych – wykład/1st
Algorytmy i Struktury Danych – wykład/1st
DelMin_B_Heap
(
H
)
Znajdź
(korzeń
x
z minimalnym kluczem na
liście korzeni
)
Usuń
(
korzeń
x
z
listy korzeni
)
Odwróć
(
kolejność elementów
ze względu na stopień
na
liście synów
węzła
x
)
Utwórz
( ze
skrajnym lewym
drzewem i
odwróconą
listą synów
nowy kopiec
H1
)
.
H
=
Union_B_Heap
(
H
,
H1
)
return
x
Dec_B_Heap
(
H, x, k
)
if
k >
key
[x]
then
Error( zla wartość klucza)
key[x] = k
y = x
z =
p
[y]
while
( z ≠ NULL
and
key[y] < key[z] )
do
Swap( key[y], key[z] )
y = z; z = p[y]
//
operacja Swap realizowana jest na wartościach
wszystkich pól.
W pętli
while
klucz węzła
y
(
syn
)
porównywany
jest z kluczem węzła
z
(
Ojciec
).
JeŜeli naruszony jest porządek kopcowy to:
-zamieniany jest klucz syna z Ojcem,
-wskaźnik
y
jest przesunięty o jeden poziom
w górę drzewa do
z
,
-rozpoczyna się nowa iteracja.
nodeBinT
struc {
nodeBinT
*
p
arent;
typK
key
;
int
degree
;
nodeBinT
*
child
;
nodeBinT
*
sibling
;
typData Data
;
}
ZłoŜoność obliczeniowa
wynosi
O
(
lg(n)
).
14
11
15
41
36
10
18
26
19
33
21
12
16
55
(
)
28
22
29
17
14
11
15
41
36
10
18
25
26
19
33
21
12
16
55
28
29
17
41
36
18
25
26
19
33
21
12
16
55
28
22
29
17
14
11
15
14
11
15
25
26
26
19
33
19
33
10
12
12
16
16
Odwrócona lista synów węzła
28
28
21
21
29
17
29
17
25
25
Rys. 11.7. Zmniejszanie wartości klucza
26
21
12
36
19
16
41
28
18
28
22
29
17
11.2.7. Usunięcie węzła
Funkcja
Del_B_Heap
(
H
,
x
) usuwa węzeł z zawartością, poprzez
przypisanie mu wartości
–inf
.
Węzeł z kluczem
–inf
jest wypychany w górę aŜ do korzenia,
poczym korzeń jest usuwany. ZłoŜoność obliczeniowa
O
(
lg(n)
).
55
Del_B_Heap
(
H
,
x
)
Dec_B_Heap(H, x,
–inf
)
DelMin_B_Heap(H)
25
i
jak na Rys.9.31
28
18
36
41
26
19
55
21
12
16
28
22
29
17
25
Rys. 11.6. Usuwanie węzła z minimalnym kluczem
ZłoŜoność obliczeniowa
wynosi
O
(
lg(n)
)
.
Rys. 11.8. Usuwanie klucza
125
126
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
11.3. Kopce Fibonacciego
Kopce Fibonacciego zostały wynalezione przez Fredmana i Tarjana w 1984 roku.
Kopiec Fibonacciego to
lista drzew
, z których kaŜde spełnia warunek kopca.
Katedra Aparatów Elektrycznych
Alg11
Algorytmy i Struktury Danych – wykład/1st
Algorytmy i Struktury Danych – wykład/1st
Dr J. Dokimuk
è
Idea operacji na kopcach Fibonacciego:
maksymalnie
opóźnić
reorganizację jego struktury.
Pozwala to
magazynować
potencjał, który w odpowiednim momencie jest zuŜywany na
bardziej czasochłonne operacje.
Taka metodyka amortyzuje
całkowity
czas
operacji wykonywanych na kopcu czyniąc go względnie niskim.
Nie
są to drzewa dwumianowe i
NIE
są uporządkowane względem
stopni
korzeni.
Niech w drzewie dwumianowym nieuporządkowanym korzeń ma stopień
k
to synowie
korzenia, są korzeniami poddrzew o stopniach
0
,
1
,…,
k-1
, ułoŜonymi w dowolnej kolejności.
Atrybuty kopca
Fibonacciego
H
:
MIN
[
H
]
wskaźnik do korzenia drzewa zawierającego
najmniejszy
klucz,
jeśli kopiec
H
jest pusty, to
MIN[
H
]
=
NULL
.
n
[
H
]
liczba węzłów naleŜących aktualnie do
H
.
Korzenie drzew w kopcu Fibonacciego połączone
są
za pomocą wskaźników
left
i
right
w
cykliczną listę dwukierunkową, zwaną listą korzeni kopca Fibonacciego.
Kolejność drzew na liście korzeni jest dowolna.
+
+
Wstawiając
nowy węzeł lub łącząc dwa kopce
,
nie
skleja się
drzew w kopcu Fibonacciego.
Odkładamy to do operacji EXTRACT-MlN, kiedy musimy znaleźć nowy węzeł minimalny.
Teoretycznie są one niezwykle przydatne, gdy liczba operacji
Del_Min
oraz
Del
jest niewielka w stosunku do liczby pozostałych operacji.
Operacje na kopcu Fibonacciego, które
nie
reorganizują jego struktury:
Make_F_Heap
()
-tworzy i zwraca nowy, pusty kopiec,
Insert_F_Heap
(H, x)
-wstawia do kopca
H
węzeł
x
o danym kluczu
key
,
Min_F_Heap
(H)
-zwraca wskaźnik do węzła w kopcu
H
, który zawiera minimalny klucz,
Union_F_Heap
(H1, H2)
-łączy dwa kopce
H1
i
H2
w jeden nowy kopiec
H.
Operacje na kopcu Fibonacciego, które
reorganizacją jego strukturę
:
Del_Min_F_Heap
(H)
-usuwa z kopca
H
węzeł o minimalnym kluczu, zwraca wskaźnik do tego węzła;
Dec_F_Heap
(H, x,key)
-nadaje kluczowi w węźle
x
kopca
H
wartość
key,
nie większą od poprzedniej;
Del_F_Heap
(H, x)
-usuwa węzeł
x
z kopca
H
.
9.6.1. Tworzenie nowego kopca Fibonacciego
Funkcja
Make_F_Heap
()
rezerwuje pamięć i zwraca obiekt
H
,
reprezentujący kopiec
Fibonacciego o atrybutach:
n[H]
=
0
,
MIN[H]
=
NULL
.
PoniewaŜ
t(H)
=
0
oraz
m(H)
=
0
, potencjał pustego kopca
Φ(H)
=
0
, zatem koszt zamortyzowany
funkcji
jest równy jej kosztowi faktycznemu O(1);
11.3.2. Wstawianie węzła
Realizuje funkcja
Insert_F_Heap
(
H, x
),
dodając do
listy korzeni
nowy węzeł.
Zakłada się, Ŝe sam węzeł
x
z wartością klucza
key
został juŜ utworzony
.
Struktura węzła:
1.
p[x]
wskaźnik do Ojca,
2.
child[x]
wskaźnik do syna
któregokolwiek
,
3.
key[x]
pole kluczy,
4.
mark[x
] -czy węzeł
x
stracił
syna od ostatniej chwili, kiedy
sam został synem innego węzła
(węzeł
zaznaczony
),
4.
degree[x]
-
liczba węzłów
na
liście
synów
,
5a.
right
[
x
]
-
wskaźnik do prawego
brata,
5b.
left
[
x
]
-
wskaźnik do lewego brata
Synowie węzła
x
powiązani są
cykliczna listą dwukierunkową
.
Do analizy efektywności operacji
na kopcach Fibonacciego stosuje
się
metodę potencjału.
Oznaczenia:
t
(
H
)
-liczba drzew na liście korzeni
H
,
m
(
H
)
-liczba
zaznaczonych
węzłów w
H
.
Potencjał
kopca
Fibonacciego
H
określa zaleŜność:
Φ(H) = t(H) + 2m(H)
Potencjał zbioru kopców Fibonacciego jest sumą potencjałów kopców składowych.
Jednostka potencjału moŜe opłacić wykonanie pewnej stałej pracy, przy czym wielkość tej stałej
jest na tyle duŜa, Ŝeby pokryć koszt dowolnej spośród występujących w algorytmach
operacji wykonywalnych w czasie stałym.
Są ulepszeniem kopców dwumianowych, co pozwoliło uzyskać stały,
zamortyzowanym
koszt
operacji
DecreaseKey
, dominującej w algorytmie Dijkstry i podobnych.
Dla grafów gęstych stały
zamortyzowany
czas wykonania
DecreaseKey
jest po zsumowaniu
lepszy niŜ czas
O(lg(n))
wykonania tej operacji na kopcach binarnych lub dwumianowych.
Asymptotycznie najszybsze algorytmy wyznaczające minimalne drzewo rozpinające lub
najkrótsze ścieŜki z ustalonego węzła wykorzystują kopce Fibonacciego
.
Jednak
złoŜona
implementacja kopców Fibonacciego powoduje, Ŝe w większości
zastosowań wygodniej jest uŜywać zwykłych kopców binarnych.
Insert_F_Heap
(
H,
x
)
p[x] = NULL; child[x] = NULL
degree[x] = 0
left[x] = x; right[x] = x
mark[x] = FALSE
Połącz
(listę korzeni korzeni
H
z
x
)
if
(MIN[X]=NULL) or (key[x]<key[MIN[H]])
then
MIN[H] = x
// ewentualna aktualizacja wskaźnika
n[H] = n[H]+1
// sygnalizacja dodania nowego węzła
.
Rys. 11.9. Kopiec Fibonacciego
Węzeł
x
staje się drzewem z własnością kopca, po
dodaniu do listy korzeni, zostaje
lewym
bratem
korzenia.
*
Rys. 11.10. Wstawianie węzła
Funkcja
nie
sklejać drzew w kopcu Fibonacciego.
Dla
k
kolejnych operacji
Insert
do listy korzeni zostanie dodanych
k
drzew
jednowęzłowych.
Wykonanie operacji
Insert
zwiększa potencjał kopca o 1 w stosunku do wartości pierwotnej.
Faktyczny koszt
Insert
wynosi O(1), zatem koszt zamortyzowany to O(1) + 1 = O(1).
11.3.3. Wyszukiwanie węzła minimalnego
Wskaźnik
MIN[H]
wskazuje na węzeł minimalny w kopcu
Fibonacciego H
MoŜna go znaleźć w faktycznym czasie
O(1).
Potencjał kopca
H
przy tej operacji nie zmienia się, zatem koszt zamortyzowany jest równy
kosztowi faktycznemu O(1).
127
128
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
11.3.4. Łączenie dwóch
kopców
Fibonacciego
Funkcja
Union_F_Heap
(
H1, H2
)
łączy dwa kopce
H1
i
H2
w jeden nowy kopiec
H
,
poprzez połączenie
listy korzeni
.
Katedra Aparatów Elektrycznych
Alg11
Dr J. Dokimuk
2gi:
konsolidacja listy drzew w wyniku której wszystkie korzenie na liście będą
miały
róŜne stopnie
.
Wykonuje się przejście przez listę korzeni i łączenie drzew jednakowego
stopnia, uaktualniając wskaźnik do korzenia zawierającego najmniejszy klucz.
Realizuje funkcja
Consolidate
(
H
)
.
MoŜna ją zrealizować w czasie proporcjonalnym do liczby konsolidowanych drzew,
wykorzystując
Tablicę
indeksowaną stopniami
korzeni.
Redukcja liczby drzew w kopcu, to wielokrotne powtarzanie
poniŜszych
operacji:
(aŜ kaŜdy korzeń na liście będzie miał
inną
wartości pola
degree
)
1.
Znajdź
na liście korzeni dwa węzły
x
i
y
tego samego stopnia, przy czym
key
[
x
]
≤ key
[
y
].
2.
Dołącz
(
y
do
x
):
usuń
y
z listy korzeni i uczyń go synem
x
(realizuje funkcja Link_F_Heap).
Wartość
degree[x]
jest zwiększana o 1, a
y
przestaje być
zaznaczone
(jeśli był).
Tablica
A
[
k
]
indeksowana stopniami
korzeni przechowuje wskaźnik do korzenia stopnia
k
w
przetworzonej części listy, albo NULL, jeśli w tej części listy korzenia o stopniu
k
nie ma.
Algorytmy i Struktury Danych – wykład/1st
Algorytmy i Struktury Danych – wykład/1st
Kopce
H1
i
H2
zostają zniszczone.
Union_F_Heap
(
H1, H2
)
H
=
Make_F_Heap()
MIN[
H
] = MIN[
H1
]
// wstaw stary kopiec H1 do nowego
H
Sklej
(listę korzeni
H2
z listą korzeni
H
)
if
(MIN[H1]==NULL) or (MIN[H2]<>NULL and MIN[H2]<MIN[H1])
then
MIN[H] = MIN[H2]
n[H] = n[H1] + n[H2]
Zwolnij_Pamięć
(H1 i H2)
return
H
Nie występuje porządkowanie względem stopni ani eliminowanie powtórzeń.
*
Inaczej: jeŜeli
A[k] = y
, to
y
jest aktualnie
korzeniem
o wartości pola
degree[y] = k
.
(każdy węzeł na liście korzeni )
( )
3 przebiegi pętli
(wiersz 211)
po 1szym przejściu pętli
łączenie
(
)
0 1 2 3 4
0 1 2 3 4
Odłaczenie węzła
od listy korzeni
e
(d)
(c)
Rys. 11.11. Łączenie dwóch kopców Fibonacciego
w,x
w,x
w,x
18
52
38
18
52
38
Zmiana potencjału
kopca jest równa zero, gdyŜ nowopowstały kopiec
H
jest strukturą, której lista
korzeni powstała poprzez
złaczenie
list korzeni kopców
H1
i
H2
.
Tym samym
t(H)
=
t(H1) + t(H2)
, zaś liczba węzłów
zaznaczonych
równieŜ nie ulega zmianie,
poniewaŜ struktura drzew po złączeniu kopców H1 i H2 pozostaje niezmieniona.
Koszt zamortyzowany operacji
Union
jest równy kosztowi faktycznemu O(1).
11.3.5. Usuwanie węzła minimalnego
Funkcja
Del_Min_F_Heap
(
H
)
usuwa węzeł z kluczem minimalnym i
dokonuje kompletnej
reorganizacji
struktury kopca Fibonacciego.
39
41
30
26
46
w
23
39
41
30
26
46
35
35
w A[3] umieszczono
wskaźnik do węzła 7
węzeł dołączony do ,
wskazywanego przez
0 1 2 3 4
0 1 2 3 4
( )
( )
x
18
52
38
18
52
38
Jej działanie jest
dwu
etapowe.
1szy:
usunięcie węzła
MIN
imum i dodanie
wszystkich jego synów do listy korzeni.
Jeśli
z
= NULL to kopiec Fibonacciego jest juŜ pusty i
zadanie jest zakończone.
Pętla
for
usuwa węzeł
z
z kopca
H
, i wszystkich jego
synów wstawia na listę korzeni.
Jeśli
z
=
right[
z
],
to
z
był jedynym węzłem na liście
korzeni i nie miał synów, więc naleŜy zazna-
czyć, Ŝe kopiec Fibonacciego jest pusty;
Del_Min_F_Heap
(
H
)
z
= MIN[H] //pamiętanie wsk do węzła min
if
(
z
= NULL)
then return
z
for
kaŜdy syn
x
węzła
z
do
Dodaj
(
x
do listy korzeni
H
)
p[
x
] = NULL
Usuń
(
z
z listy korzeni
H
)
if
(z=right[z])
then
MIN[H] = NULL
else
MIN[H] = right[z]
Consolidate
(
H
)
n[H] = n[H]1
return
z
39
41
26
46
39
41
24
17
23
w
17
23
w
26
46
30
35
30
35
4ry kolejne przebiegi pętli
0 1 2 3 4
0 1 2 3 4
0 1 2 3 4
l
(j)
w,x
(i)
w,x
( )
( )
( )
w,x
w,x
18
38
18
52
38
18
38
41
w
przeciwnym
razie do wskaźnika
min
[
H
]
przypisuje się węzeł
right
[
z
].
21
39
24
17
23
39
41
24
17
23
21
39
41
29
52
52
26
46
30
26
46
30
MIN(
MIN
H)
po usunięciu MIN
(
b)
MIN
MIN(
H)
(
a)
Del_Min_F_Heap( )
35
35
23
223
23
7
21
221
21
3
17
117
17
24
224
24
23
223
23
7
21
221
21
18
52
38
17
117
17
24
224
24
Rys. 11.12.
Usuwanie węzła minimalnego: 2gi etap
– przetwarzanie od węzła MIN po wskaźnikach
right
39
41
30
26
46
Po skróceniu listy korzeni funkcja
Consolidate
(
H
)
kończy działanie.
Zmniejszana jest wartość
n[H]
i zwracany zostaje wskaźnik do usuniętego węzła
z
.
Zamortyzowany koszt operacji wynosi O(D(
n
)) co moŜna oszacować na O(lg(n)).
18
52
38
30
26
46
35
39
41
35
Plik z chomika:
kendzior21
Inne pliki z tego folderu:
Alg0.pdf
(69 KB)
Alg10.pdf
(175 KB)
Alg11.pdf
(429 KB)
Alg1.pdf
(259 KB)
Alg12.pdf
(331 KB)
Inne foldery tego chomika:
Podstawy & Algorytmy
Zgłoś jeśli
naruszono regulamin