wyklad6 drukuj, WIMiIP IS, Algorytmy i Struktóry Danych, Wykłady
[ Pobierz całość w formacie PDF ]
Kolejkipriorytetowe.
Zastosowania.
Kolejkapriorytetowa
to struktura danych reprezentuj¡ca zbiór
dynamiczny
S
, którego ka»dy element ma przyporz¡dkowan¡
warto±¢, zwan¡
kluczem
. Na
kolejcepriorytetowejtypumax
mo»na wykona¢ nast¦puj¡ce operacje:
I
INSERT(
S
,
x
) dodaje element
x
do zbioru
S
.
I
MAXIMUM(
S
) daje w wyniku element o najwi¦kszym kluczu.
I
EXTRACT-MAX(
S
) usuwa i daje w wyniku element o
najwi¦kszym kluczu.
I
INCREASE-KEY(
S
,
x
,
k
) zmienia warto±¢ klucza elementu
x
na now¡ warto±¢
k
, o której zakłada si¦, »e jest nie mniejsza
ni» dotychczasowa warto±¢ klucza.
Jednym z zastosowa« kolejki priorytetowej typu max jest
szeregowanie zada«, na przykład na współdzielonym komputerze.
Elementami kolejki sa zadania, które maj¡ by¢ wykonane. Klucze
oznaczaj¡ priorytety zada« wzgl¦dem siebie. Kiedy zadanie ko«czy
si¦ lub zostaje przerwane, zadanie o najwi¦kszym priorytecie jest
wybierane spo±ród zada« czekaj¡cych za pomoc¡ operacji
EXTRACT-MAX. Nowe zadanie mo»e by¢ dodane do kolejki w
dowolnej chwili za pomoc¡ operacji INSERT.
Kolejki priorytetowej typu min mo»na u»y¢ jako symulatora
zdarze«. Elementami s¡ zdarzenia, ka»de z przyporz¡dkowanym
czasem wyst¡pienia, który słu»y jako klucz. Program symulacyjny
korzysta w ka»dym kroku z operacji EXTRACT-MIN do wybrania
zdarzenia, które b¦dzie symulował. Kiedy generowane s¡ nowe
zdarzenia, zostaj¡ one dodane do kolejki za pomoc¡ operacji
INSERT.
Na
kolejcepriorytetowejtypumin
mo»na wykona¢ analogiczne
operacje INSERT, MINIMUM, EXTRACT-MIN i
DECREASE-KEY.
Kopiecjakokolejkapriorytetowa.
Funkcja HEAP-EXTRACT-MAX stanowi implementacje operacji
EXTRACT-MAX. Podobnie jak w procedurze HEAPSORT,
element o najwi¦kszym kluczu
A
[
1
]
zostaje „usuniety” z kopca, a
na jego miejsce zostaje przeniesiony ostatni element
A
[
n
]
.
Nast¦pnie w tablicy
A
[
1
..
n
−
1
]
zostaje przywrócona własno±¢
kopca typu max za pomoc¡ MAX-HEAPIFY.
Do implementacji kolejki priorytetowej mo»emy u»y¢ kopca
(takiego samego typu max/min). Dla prostoty b¦dziemy
uto»samia¢ elementy kolejki z ich kluczami, które b¦dziemy
przechowywa¢ w tablicy
A
traktowanej jako kopiec. W sytuacji,
gdy elementami kolejki s¡ bardziej zło»one obiekty (np. rekordy),
to w tablicy przechowujemy wska¹niki do tych obiektów.
HEAP-EXTRACT-MAX(
A
,
n
) //
n
=
rozmiar kopca
1.
begin
2.
if
n
<
1
3.
thenerror
„kopiec pusty”
4.
elsebegin
5.
max
:=
A
[
1
]
;
6.
A
[
1
]:=
A
[
n
]
;
7.
n
:=
n
−
1;
8. MAX-HEAPIFY(
A
,
n
,
1);
9.
return
max
;
10.
end;
9.
end;
Funkcja HEAP-MAXIMUM implementuje operacj¦ MAXIMUM w
czasie
O
(
1
)
:
HEAP-MAXIMUM(
A
)
1.
begin
2.
return
A
[
1
]
;
3.
end;
Czas działania funkcji HEAP-EXTRACT-MAX wynosi
O
(
log
n
)
,
poniewa» wykonuje ona stał¡ ilo±¢ operacji elementarnych poza
procedur¡ MAX-HEAPIFY w wierszu 7, która działa w czasie
O
(
log
n
)
.
HEAP-INCREASE-KEY(
A
,
i
,
k
)
1.
begin
2. if
k
<
A
[
i
]
3.
thenerror
„nowy klucz jest mniejszy ni» klucz aktualny”
4.
elsebegin
5.
A
[
i
]:=
k
;
6.
while
i
>
1 i
A
[
parent
(
i
)]
<
A
[
i
]
do
7.
begin
8. zamie«
A
[
i
]
z
A
[
parent
(
i
)]
;
9.
i
:=
parent
(
i
)
;
10.
end;
11.
end;
12.
end;
Procedura HEAP-INCREASE-KEY jest implementacj¡ operacji
INCREASE-KEY. Element, którego klucz ma zosta¢ zwi¦kszony,
jest okre±lony przez indeks
i
w tablicy.
Na pocz¡tku procedury klucz
A
[
i
]
przyjmuje now¡ warto±¢.
Poniewa» zwi¦kszenie klucza mogło naruszy¢ własno±¢ kopca typu
max, zatem przechodzimy ±cie»k¦ od tego w¦zła w kierunku
korzenia w celu znalezienia wła±ciwego miejsca dla nowego,
zwi¦kszonego klucza (porównaj z p¦tl¡ w wierszach 6-10 procedury
INSERTION-SORT).
HEAP-INCREASE-KEY(
A
,
9
,
10) dla
A
=[
12
,
9
,
7
,
8
,
5
,
6
,
2
,
1
,
3
,
4
]
.
i=9, k=10
Liczba iteracji p¦tli
while
jest nie wi¦ksza ni» długo±¢ ±cie»ki od
w¦zła uaktualnianego w wierszu 5 do korzenia, która jest nie
wi¦ksza ni» wysoko±¢ kopca, czyli
b
log
n
c
. Zatem czas działania
procedury HEAP-INCREASE-KEY na
n
-elementowym kopcu
wynosi
O
(
log
n
)
.
12
12
9
7
9
7
8
5 6
2
8
5 6
2
1
3
4
1
10
4
Poprawno±¢ procedury HEAP-INCREASE-KEY mo»na wykaza¢,
korzystaj¡c z nast¦puj¡cego niezmiennika p¦tli:
Podczas ka»dego sprawdzania warunku wej±cia do p¦tli
while
w
wierszu 6 tablica
A
[
1
..
n
]
spełnia własno±¢ kopca typu max z co
najwy»ej jednym wyj¡tkiem:
A
[
i
]
mo»e by¢ wi¦ksze ni»
A
[
parent
(
i
)]
.
12
12
9
7
10
7
10
5 6
2
9
5 6
2
1 8 4
1 8 4
Inicjowanie:
Tablica wej±ciowa jest kopcem typu max. Po zmianie
warto±ci
A
[
i
]
na warto±¢ wi¦ksz¡ w wierszu 5 mo»e by¢
A
[
i
]
>
A
[
parent
(
i
)]
, a w pozostałych w¦złach zostaje zachowana
własno±¢ kopca.
Utrzymanie:
Załó»my, »e niezmiennik jest prawdziwy przed
sprawdzeniem warunku, który jest spełniony. Wtedy
A
[
parent
(
i
)]
<
A
[
i
]
i po zamianie
A
[
i
]
z
A
[
parent
(
i
)]
w wierszu 8,
w w¦¹le
i
b¦dzie spełniona własno±¢ kopca typu max. Poniewa»
warto±¢
A
[
parent
(
i
)]
zmieniła si¦ na wi¦ksz¡, wi¦c własno±¢ kopca
w w¦¹le
parent
(
i
)
mogła zosta¢ utracona. Pozostałe w¦zły nadal
spełniaj¡ własno±¢ kopca. Zamiana
i
na
parent
(
i
)
powoduje, »e
niezmiennik b¦dzie prawdziwy przed kolejnym sprawdzeniem
warunku w wierszu 6.
Zako«czenie:
Podczas ostatniego sprawdzania warunek w wierszu
6 nie jest spełniony, to znaczy, »e
i
=
1 lub
A
[
i
]
A
[
parent
(
i
)]
. W
obu przypadkach na mocy niezmiennika własno±¢ kopca typu max
jest spełniona dla ka»dego w¦zła tablicy
A
[
1
..
n
]
nie b¦d¡cego
korzeniem.
Procedura MAX-HEAP-INSERT jest implementacj¡ operacji
INSERT. Jej argumentami s¡ tablica
A
, rozmiar kopca
n
oraz klucz
k
nowego elementu, który ma by¢ dodany do kopca. Najpierw
dodajemy nowy li±¢ o kluczu
−1
, a nast¦pnie za pomoc¡
HEAP-INCREASE-KEY zmieniamy warto±¢ klucza na wła±ciw¡ i
odtwarzamy własno±¢ kopca typu max.
MAX-HEAP-INSERT(
A
,
n
,
k
)
1.
begin
2.
n
:=
n
+
1;
3.
A
[
n
]:=
−1
;
4. HEAP-INCREASE-KEY(
A
,
n
,
k
);
5.
end;
Czas działania funkcji MAX-HEAP-INSERT wynosi
O
(
log
n
)
,
poniewa» wykonuje ona stał¡ ilo±¢ operacji elementarnych poza
procedur¡ HEAP-INCREASE-KEY w wierszu 4., która działa w
czasie
O
(
log
n
)
.
Podsumowanie.
MAX-HEAP-INSERT(
A
,
10
,
10).
12
12
9
7
9
7
8
5 6
2
8
5 6
2
Implementacja w postaci kopca umo»liwia wykonanie wszystkich
operacji kolejki priorytetowej na zbiorze
n
-elementowym w czasie
O
(
log
n
)
.
1 3 4
−1
1 3 4
10
12
12
9
7
10
7
8
10
6
2
8
9 6
2
1 3 4 5
1 3 4 5
[ Pobierz całość w formacie PDF ]