wyklad5 drukuj, WIMiIP IS, Algorytmy i Struktóry Danych, Wykłady
[ Pobierz całość w formacie PDF ]
Kopce.
Załó»my, »e
A
jest tablic¡ reprezentuj¡c¡ kopiec. Korzeniem
drzewa jest
A
[
1
]
, a maj¡c dany indeks
i
w¦zła, mo»na łatwo
obliczy¢ indeksy jego ojca
parent
(
i
)
, lewego syna
left
(
i
)
i prawego
syna
right
(
i
)
:
Kopiec(binarny)
to tablicowa struktura danych, któr¡ mo»na
traktowa¢ jako drzewo binarne, pełne na wszystkich poziomach z
wyj¡tkiem by¢ mo»e najni»szego, który jest wypełniony od lewej
strony do pewnego miejsca.
parent
(
i
)=
b
i
/
2
c
,
left
(
i
)=
2
i
,
right
(
i
)=
2
i
+
1
.
Na przykład tablicy
[
10
,
9
,
8
,
5
,
6
,
4
,
7
,
2
,
1
,
3
]
odpowiada drzewo
Lemat5.1
Kopiec
n
-elementowy ma wysoko±¢
b
log
n
c
.
Dowód:
Niech
h
b¦dzie wysoko±ci¡ kopca. Poniewa» pełne drzewo
binarne o wysoko±ci
h
zawiera 2
h
+
1
−
1 elementów (Lemat 2.1),
wi¦c 2
h
n
<
2
h
+
1
, st¡d
h
log
n
<
h
+
1, czyli
h
=
b
log
n
c
.
Lemat5.2
Li±cie
n
-elementowego kopca to w¦zły o indeksach
b
n
/
2
c
+
1
,
b
n
/
2
c
+
2
,...,
n
.
Dowód:
Li±¢ to w¦zeł, który nie ma synów. Zatem
i
jest indeksem
li±cia wtedy i tylko wtedy, gdy
left
(
i
)
>
n
, czyli
i
>
n
/
2.
10
9
8
5
6
4
7
2 1 3
Przywracaniewłasno±cikopca.
Kopce wyst¦puj¡ w dwóch odmianach: typu max i typu min.
Własno±¢kopcatypumax:
dla ka»dego w¦zła
i
, który nie jest korzeniem, zachodzi
A
[
parent
(
i
)]
A
[
i
]
.
MAX-HEAPIFY jest procedur¡ słu»¡c¡ do przywracania własno±ci
kopca typu max.
Jej danymi wej±ciowymi s¡: tablica
A
, rozmiar kopca
n
oraz indeks
i
n
.
Najwi¦kszy element kopce typu max jest umieszczony w korzeniu,
a poddrzewa ka»dego w¦zła zawieraj¡ warto±ci nie wi¦ksze ni»
warto±¢ w tym w¦¹le.
Własno±¢kopcatypumin:
dla ka»dego w¦zła
i
, który nie jest korzeniem, zachodzi
A
[
parent
(
i
)]
A
[
i
]
.
Zakładamy, »e lewe i prawe poddrzewa w¦zła o indeksie
i
s¡
kopcami typu max, ale element
A
[
i
]
mo»e by¢ mniejszy od którego±
ze swoich synów, przez co narusza własno±¢ kopca typu max.
W wyniku działania MAX-HEAPIFY, element
A
[
i
]
„spływa” w dół
drzewa tak, »e poddrzewo o korzeniu w w¦¹le
i
staje si¦ kopcem
typu max.
Najmniejszy element kopca typu min znajduje si¦ w korzeniu.
ProceduraMAX-HEAPIFY
DziałanieMAX-HEAPIFY
MAX-HEAPIFY(
A
,
n
,
i
)
1.
begin
2.
l
:=
left
(
i
)
;
3.
r
:=
right
(
i
)
;
4.
if
l
n
and
A
[
l
]
>
A
[
i
]
5.
then
largest
:=
l
6.
else
largest
:=
i
;
7.
if
r
n
and
A
[
r
]
>
A
[
largest
]
8.
then
largest
:=
r
;
9.
if
largest
6
=
i
then
10.
begin
11. zamie«
A
[
i
]
z
A
[
largest
]
;
12. MAX-HEAPIFY(
A
,
n
,
largest
);
13.
end;
14.
end;
W ka»dym kroku jest wybierany najwi¦kszy z elementów
A
[
i
]
,
A
[
left
(
i
)]
,
A
[
right
(
i
)]
, a jego indeks jest zachowywany w zmiennej
largest
.
Je±li najwi¦kszy jest
A
[
i
]
, to poddrzewo o korzeniu w
i
jest kopcem
typu max i procedura si¦ zatrzymuje.
W przeciwnym wypadku jeden z synów jest najwi¦kszym
elementem i nast¦puje zamiana
A
[
i
]
z
A
[
lergest
]
, co powoduje »e
w¦zeł
i
i jego synowie spełniaj¡ własno±¢ kopca typu max.
W¦zeł
largest
ma jednak teraz warto±¢
A
[
i
]
i dlatego poddrzewo o
korzeniu
largest
mo»e nie spełnia¢ własno±ci kopca typu max.
eby to naprawi¢ wywołujemy MAX-HEAPIFY rekurencyjnie na
tym poddrzewie.
Przykład: działanie procedury MAX-HEAPIFY(
A
,
10
,
2)
i l r largest A
2 4 5 4
[
10
,
3
,
8
,
9
,
6
,
4
,
7
,
2
,
5
,
1
]
4 8 9 9
[
10
,
9
,
8
,
3
,
6
,
4
,
7
,
2
,
5
,
1
]
9 18 19 9
[
10
,
9
,
8
,
3
,
6
,
4
,
7
,
2
,
3
,
1
]
CzasdziałaniaMAX-HEAPIFY
Oznaczmy:
c
- ł¡czny czas wykonania instrukcji w wierszach 2–11,
T
(
h
)
- pesymistyczny czas działania procedury MAX-HEAPIFY na
drzewie o wysoko±ci
h
.
Poddrzewo, na którym wywołujemy MAX-HEAPIFY rekurencyjnie
w wierszu 12 ma wysoko±¢
h
−
1, st¡d
10
10
3
8
9
8
9
6
4
7
3
6 4
7
2 5 1
2 5
1
T
(
h
)
c
+
T
(
h
−
1
)
.
10
Łatwo wykaza¢ przez indukcj¦, »e
T
(
h
)
c
(
h
+
1
)
, czyli
T
(
h
)=
O
(
h
)
.
St¡d i z Lematu 5.1 otrzymujemy, »e MAX-HEAPIFY działa na
drzewie rozmiaru
k
w pesymistycznym czasie
O
(
log
k
)
.
9
8
5
6 4
7
2
3
1
Budowaniekopca.
Działanie BUILD-MAX-HEAP dla
A
=[
1
,
4
,
7
,
3
,
10
,
6
,
2
,
8
,
9
,
5
]
.
Na kolejnych rysunkach pokazano drzewo przed wywołaniem
MAX-HEAPIFY w wierszu 3. Element o indeksie
i
zaznaczono na
czerwono.
Procedury MAX-HEAPIFY mo»emy u»y¢ do przekształcenia
dowolnej tablicy
A
[
1
..
n
]
w kopiec typu max.
Na mocy Lematu 5.2 wszystkie elementy podtablicy
A
[(
b
n
/
2
c
+
1
)
..
n
]
s¡ li±¢mi, zatem ka»dy z nich jest ju»
1-elementowym kopcem.
Procedura BUILD-MAX-HEAP przechodzi przez pozostałe w¦zły i
wywołuje w ka»dym z nich MAX-HEAPIFY.
1
1
4
7
4
7
3
10
6
2
3
10 6
2
8 9 5
8 9 5
BUILD-MAX-HEAP(
A
)
1.
begin
2.
for
i
:=
b
n
/
2
c
downto
1
do
3.
1
1
4
7
4
7
MAX-HEAPIFY(
A
,
n
,
i
);
9
10 6
2
9
10 6
2
4.
end;
8 3 5
8 3 5
1
10
Inicjowanie:
Podczas pierwszego sprawdzania jest
i
=
h
n
/
2
i
.
Ka»dy z w¦złów o indeksach
h
n
/
2
i
+
1
,...,
n
jest li±ciem na mocy
Lematu 5.2, jest wi¦c korzeniem trywialnego kopca typu max.
Utrzymanie:
Zauwa»my, »e synowie w¦zła
i
maj¡ indeksy wi¦ksze
ni»
i
, wi¦c na mocy niezmiennika s¡ korzeniami kopców typu max.
Zatem po wywołaniu MAX-HEAPIFY(
A
,
n
,
i
)
, w¦zeł
i
b¦dzie
kopcem typu max, a w¦zły
i
+
1
,...,
n
nadal b¦d¡ korzeniami
kopców typu max. Niezmiennik p¦tli b¦dzie wiec spełniony
podczas nast¦pnego sprawdzania warunku p¦tli.
Zako«czenie:
Podczas ostatniego sprawdzania
i
=
0. Na mocy
niezmiennika, ka»dy z w¦złów 1
,...,
n
jest korzeniem kopca typu
max. W szczególno±ci jest nim w¦zeł o indeksie 1, czyli całe
drzewo jest kopcem typu max.
10
7
9
7
9
5 6
2
8
5 6
2
8 3 4
1 3 4
Aby pokaza¢, »e procedura BUILD-MAX-HEAP działa poprawnie,
wyka»emy nast¦puj¡cy niezmiennik p¦tli:
Podczas ka»dego sprawdzania warunku p¦tli
for
, ka»dy z w¦złów o
indeksach
i
+
1
,
i
+
2
,...,
n
jest korzeniem w¦zła typu max.
CzasdziałaniaBUILD-MAX-HEAP.
Ustalmy dowolny w¦zeł
x
kopca rozmiaru
n
i niech
d
oznacza jego
gł¦boko±¢, a
h
wysoko±¢, to znaczy wysoko±¢ poddrzewa o
korzeniu
x
. Wtedy
d
+
h
jest wysoko±ci¡ całego kopca, czyli
d
+
h
=
b
log
n
c
.
Dowolne drzewo binarne ma co najwy»ej 2
d
w¦złów o gł¦boko±ci
d
, a zatem
n
-elementowy kopiec ma co najwy»ej
Zauwa»my, »e szereg
1
X
h
2
h
h
=
1
jest zbie»ny (np. na mocy kryterium Cauchy’ego). Oznaczaj¡c
przez
s
jego sum¦ otrzymujemy, »e dla dowolnego
n
zachodzi
2
b
log
n
c−
h
n
/
2
h
b
log
n
c
h
2
h
<
s
,
w¦złów o gł¦boko±ci
h
.
Czas działania procedury MAX-HEAPIFY wywołanej w w¦¹le o
wysoko±ci
h
wynosi
O
(
h
)
, zatem pesymistyczny czas działania
BUILD-MAX-HEAP dla tablicy
n
-elementowej szacuje si¦ przez
h
=
1
czyli
T
(
n
)=
O
(
n
)
.
Zatem pesymistyczny czas działania procedury BUILD-MAX-HEAP
dla tablicy
n
-elementowej wynosi
O
(
n
)
.
b
log
n
c
n
0
@
n
b
log
n
c
h
2
h
1
A
.
T
(
n
)
2
h
O
(
h
)=
O
h
=
1
h
=
1
Sortowanieprzezkopcowanie(heapsort).
ProceduraHEAPSORT
Algorytm heapsort sortuje tablic¦
A
[
1
..
n
]
w nast¦puj¡cy sposób.
I
Najpierw tablica jest przekształcana w kopiec typu max, za
pomoc¡ BUILD-MAX-HEAP.
I
Wtedy
A
[
1
]
jest najwi¦kszym elementem, wi¦c umieszczamy
go na swoim miejscu, zamieniaj¡c z
A
[
n
]
.
I
Je»eli teraz „wyrzucimy” ostatni w¦zeł z kopca, to otrzyman¡
tablic¦
A
[
1
..
n
−
1
]
łatwo przekształci¢ w kopiec typu max.
Poniewa» synowie korzenia s¡ wierzchołkami kopca typu max,
wiec wystarczy wywoła¢ MAX-HEAPIFY(
A
,
n
−
1
,
1
)
.
I
Ten proces jest powtarzany dla coraz mniejszych kopców, a»
do uzyskania kopca rozmiaru 2.
HEAPSORT(
A
)
1.
begin
2. BUILD-MAX-HEAP(
A
);
3.
for
i
:=
n
downto
2
do
4.
begin
5. zamie«
A
[
1
]
z
A
[
i
]
;
6. MAX-HEAPIFY(
A
,
i
−
1
,
1);
7.
end;
8.
end;
X
X
X
Poprawno±¢HEAPSORT
Aby pokaza¢, »e HEAPSORT poprawnie sortuje tablic¦, wyka»emy
nast¦puj¡cy niezmiennik p¦tli:
Podczas ka»dego sprawdzania warunku p¦tli
for
podtablica
A
[
1
..
i
]
jest kopcem typu max zawieraj¡cym
i
najmniejszych elementów z
tablicy wej±ciowej, a
A
[
i
+
1
..
n
]
zawiera posortowanych
n
−
i
najwi¦kszych elementów z tablicy wej±ciowej.
Utrzymanie:
Załó»my, »e niezmiennik jest spełniony na pocz¡tku iteracji.
Poniewa»
A
[
1
..
i
]
jest kopcem typu max zawieraj¡cym
i
najmniejszych elementów z tablicy wej±ciowej, wi¦c
A
[
1
]
jest
najwi¦kszym z
i
najmniejszych elementów.
Zamiana
A
[
1
]
z
A
[
i
]
w wierszu 5 powoduje, »e
A
[
i
..
n
]
zawiera
posortowanych
n
−
(
i
−
1
)
najwi¦kszych elementów z tablicy
wej±ciowej.
Wywołanie MAX-HEAPIFY(
A
,
i
−
1
,
1) w wierszu 6 powoduje
odtworzenie własno±ci kopca typu max w podtablicy
A
[
1
..
i
−
1
]
,
która teraz zawiera
i
−
1 najmniejszych elementów tablicy
wej±ciowej.
Inicjowanie:
Podczas pierwszego sprawdzania jest
i
=
n
. Tablica
A
[
1
..
n
]
jest
kopcem typu max zbudowanym z elementów tablicy wej±ciowej za
pomoc¡ procedury BUILD-MAX-HEAP(
A
) w wierszu 2.
Podtablica
A
[
i
+
1
..
n
]
jest pusta.
Przykład.
Zako«czenie:
Na ko«cu mamy
i
=
1.
Na mocy niezmiennika,
A
[
1
]
jest najmniejszym elementem tablicy
wej±ciowej, a
A
[
2
..
n
]
zawiera posortowanych
n
−
1 najwi¦kszych
elementów z tablicy wej±ciowej.
Zatem cała tablica
A
[
1
..
n
]
jest posortowan¡ tablic¡ wej±ciow¡
Działanie HEAPSORT dla
A
=[
1
,
4
,
7
,
3
,
10
,
6
,
2
,
8
,
9
,
5
]
. Ka»dy
rysunek przedstawia kopiec typu max na pocz¡tku kolejnej iteracji
p¦tli
for
. Posortowan¡ cz¦±¢ tablicy nie nale»¡c¡ do kopca
zaznaczono na czerwono.
10
9
9
7
8
7
8
5 6
2
4
5 6
2
1 3 4
1 3
10
[ Pobierz całość w formacie PDF ]