algorytmy

[ Pobierz całość w formacie PDF ]
Pojęcia:
Lista (definicja rekurencyjna)
– struktura zdefiniowana na
skończonym zbiorze elementów, która albo nie zawiera
żadnych elementów i jest nazywana listą pustą, albo jest
połączeniem elementu i listy.
Liść
– węzeł nie posiadający potomków.
Operacje dominujące
– operacje charakterystyczne dla
danego algorytmu, a ich liczba jest proporcjonalna do
liczby wykonań wszystkich operacji jednostkowych w
dowolnej realizacji komputerowej danego algorytmu.
Poddrzewo
– pewien węzeł
v
(określony tu jako korzeń
tego poddrzewa) wraz ze wszystkimi swoimi potomkami.
Porządek całkowity (liniowy)
– częściowy porządek relacji
R
na zbiorze
S
, taki, że dla dowolnej pary elementów
tego zbioru (
a
,
b
) zachodzi
aRb
lub
bRa
.
Porządek częściowy
– relacja
R
na zbiorze
S
, posiadająca
właściwości:
Złożoność pamięciowa asymptotyczna
– charakter
złożoności pamięciowej przy dążeniu do wartości
granicznej wraz ze wzrostem rozmiaru zadania.
Złożoność pesymistyczna
– największa ze złożoności dla
wszystkich możliwych wejść danego rozmiaru.
Zwrotność
– dla dowolnego
a є S
, zachodzi
aRa
(
S
to zbiór,
R
to relacja).
Algorytm
– pewien przepis (sposób postępowania), który
ma prowadzić do rozwiązania określonego zadania.
Algorytm wewnętrzny
– dane są przechowywane
wyłącznie w pamięci wewnętrznej.
Algorytm zewnętrzny
– dane w przeważającej części
znajdują się poza pamięcią wewnętrzną.
Algorytmiczna dziedzina
– zbiór obiektów i dostępnych w
algorytmie pierwotnych operacji.
Algorytmu określoność
– wymóg, aby każda operacja w
algorytmie była sformułowana w sposób zapewniający
jej jednoznaczną interpretację.
Algorytmu skończoność
– algorytm powinien zakończyć
swoje działanie po wykonaniu skończonej liczby
operacji.
Algorytmu wejście
– pewne dane pobierane przez
algorytm w celu ich przetworzenia.
Algorytmu wyjście
– wynik działania algorytmu.
Algorytmu wykonywalność
– pisząc algorytm, wystarczy
się jedynie posłużyć dostępnymi poleceniami.
Antysymetryczność
– dla dowolnych
a,b є S
zachodzi: jeśli
aRb
i
bRa
, to
a = b
(
S
to zbiór,
R
to relacja).
Cykl w grafie nieskierowanym
– droga, dla której
wierzchołek początkowy jest tym samym wierzchołkiem,
co wierzchołek końcowy, wszystkie wierzchołki są różne,
a ich ilość jest większa lub równa 2.
Cykl w grafie skierowanym
– droga, dla której
wierzchołek początkowy jest tym samym wierzchołkiem,
co wierzchołek końcowy.
Drzewo binarne
– drzewo, którego każdy węzeł posiada co
najwyżej dwóch synów, z których da się wyróżnić
lewy
i
prawy
.
Drzewo binarne (definicja rekurencyjna)
– struktura
zdefiniowana na skończonym zbiorze węzłów w ten
sposób, że albo nie zawiera żadnych węzłów i jest
nazywana drzewem pustym, albo składa się z trzech
rozłącznych zbiorów węzłów: korzenia, lewego
poddrzewa i prawego poddrzewa.
Drzewo niezorientowane
– graf nieskierowany, który jest
spójny, acykliczny i posiada wyróżniony wierzchołek
nazywany korzeniem.
Drzewo pełne
– binarne drzewo, w którym istnieje liczba
k
taka, że dla każdego węzła o głębokości mniejszej niż
k
występują oba węzły będące jego synami, a każdy węzeł
o głębokości
k
jest liściem.
Drzewo przeszukiwań binarnych (BST)
– drzewo binarne,
w którym wartości kluczy są przechowywane w taki
sposób, aby spełniały tzw. własność drzewa BST, zgodnie
z którą dla dowolnego węzła
x
, jeśli
y
jest węzłem jego
lewego poddrzewa, to
key[y] ≤ key[x]
, a jeśli
y
jest
węzłem jego prawego poddrzewa, to
key[y] ≥ key[x]
.
Drzewo regularne
– binarne drzewo, w którym każdy z
węzłów jest albo liściem, albo posiada jednocześnie
lewego i prawego syna.
Drzewo uporządkowane
– drzewo, w którym zbiór synów
każdego węzła jest uporządkowany.
Drzewo zorientowane (skierowane)
– acykliczny
skierowany graf, posiadający dokładnie jeden
wierzchołek, do którego nie dochodzi żadna krawędź
(
korzeń
drzewa). Dla dowolnego wierzchołka w drzewie
tym istnieje droga prowadząca od korzenia do tego
wierzchołka i jest to droga jedyna. Każdy wierzchołek nie
będący drzewem ma dokładnie jedną krawędź
wchodzącą do niego.
Głębokość węzła
– długość drogi od korzenia do tego
węzła.
Graf
– para zbirów
G = (V, E)
, gdzie
V
jest skończonym
zbiorem wierzchołków, a
E
jest zbiorem krawędzi.
Graf acykliczny
– graf nie zawierający cykli.
Infiksowy zapis matematyczny
– tradycyjny zapis
matematyczny, gdzie operandy są oddzielone znakiem
operacji, np.
5*(((9 + 8)*(4 * 6)) + 7)
.
Kolejka
– struktura z ograniczonym dostępem, dla której
określono początek i koniec. Elementy są obsługiwane
według porządku „pierwszy przyszedł, pierwszy
wyszedł”.
Kolejka proprytetowa
– struktura przechowująca S
elementów, z których każdy ma przyporządkowaną
wartość klucza.
Kopiec (heap)
– struktura, która może być rozpatrywana
jako rodzaj „prawie pełnego” drzewa binarnego. Drzewo
to jest pełne w tym sensie, że jest wypełnione na
wszystkich poziomach z wyjątkiem bić może najniższego,
który jest wypełniony od lewej do prawej do pewnego
miejsca.
Korzeń drzewa
– wierzchołek drzewa skierowanego, do
którego nie dochodzi żadna krawędź.
Lista
– skończony ciąg elementów należących do pewnego
zbioru.
Typy operandów:
=i
– liczba całkowita i; operand tego typu nazywamy
literałem;
v(=i) = i
,
i
– zawartość rejestru o numerze
i
(
i
powinno być
nieujemne);
v(i) = c(i)
,
*i
– wartością operandu jest zawartość rejestru
j
, gdzie
j
jest liczbą nieujemną przechowywaną w rejestrze
i
(adresacja pośrednia);
v(*i) = c(c(i))
.
zwrotność,
przechodniość,
antysymetryczność.
Postfiksowy zapis matematyczny (odwrotny zapis polski)
– pośrednia postać zapisu matematycznego, w której
operandy występują zawsze przed znakiem operacji, np.
5 9 8 + 4 6 * * 7 + *
. Idealny zapis pośredni dla wyrażeń
arytmetycznych, które mają być obliczane za pomocą
stosu.
Potomek węzła
– węzeł
w
dla węzła
v
, jeśli w drzewie
zorientowanym istnieje droga prowadząca od węzła
v
do
węzła
w
. Dla drzewa niezorientowanego, węzeł
v
jest
położony wyżej w strukturze drzewa, niż węzeł
w
.
Przechodniość
– dla dowolnych
a,b,c є S
, zachodzi: jeśli
aRb
i
bRc
, to
aRc
(
S
to zbiór,
R
to relacja).
Przodek węzła
– węzeł
v
dla węzła
w
, jeśli w drzewie
zorientowanym istnieje droga prowadząca od węzła
v
do
węzła
w
. Dla drzewa niezorientowanego, węzeł
v
jest
położony wyżej w strukturze drzewa, niż węzeł
w
.
Rekurencja
– procedura, która bezpośrednio lub
pośrednio wywołuje samą siebie.
Rodzic wierzchołka
– węzeł
v
dla wierzchołka
w
w
krawędzi
(v, w) є E
w drzewie zorientowanym. W
drzewie niezorientowanym, węzeł
v
jest węzłem
położonym o jeden poziom wyżej w strukturze drzewa,
niż węzeł
w
.
Rozmiar zadania (wejścia)
– konkretna liczba
charakteryzująca objętość danych wejściowych.
Spójność grafu nieskierowanego
– każda para
wierzchołków jest połączona ścieżką (drogą).
Silna spójność grafu skierowanego
– każde dwa
wierzchołki są osiągalne jeden z drugiego.
Sterowanie
– zmiana kolejności elementów pewnego
ciągu tak, aby zostały one ustawione w porządku
niemalejącym lub nierosnącym.
Stopień wierzchołka w grafie nieskierowanym
– liczba
incydentnych z nim krawędzi.
Stopień wejściowy
– liczba krawędzi wchodzących.
Stopień wyjściowy
– liczba krawędzi wychodzących.
Stos
– struktura posiadająca ustalony element nazywany
wierzchołkiem, który jest jedynym dostępnym w danej
chwili jej składnikiem. Elementy są obsługiwane według
porządku „ostatni przyszedł, pierwszy wyszedł”.
Sumator
– rejestr r0, pełniący w obliczeniach specjalną
rolę.
Syn wierzchołka
– węzeł
w
dla wierzchołka
v
w krawędzi
(v, w) є E
w drzewie zorientowanym. W drzewie
niezorientowanym, węzeł
v
jest węzłem położonym o
jeden poziom wyżej w strukturze drzewa, niż węzeł
w
.
Ścieżka (droga) w grafie
– ciąg kolejnych wierzchołków,
przez które przechodzimy, kierując się od wierzchołka
początkowego do wierzchołka końcowego.
Taśma wejściowa
– ciąg klatek, z których każda może
zawierać liczbę całkowitą. Każdorazowo, kiedy z taśmy
wejściowej zostanie odczytana liczba, głowica czytająca
jest przesuwana o jedną pozycję w prawo.
Taśma wyjściowa
– ciąg klatek (na początku pustych), do
których maszyna może tylko zapisywać. Po zapisie do
kolejnej klatki głowica zapisująca jest przesuwana o
jedną klatkę w prawo.
Węzeł
– wierzchołek drzewa.
Wysokość drzewa
– wysokość jego korzenia.
Wysokość węzła
– maksymalna długość drogi od tego
węzła do liścia.
Złożoność czasowa
– czas potrzebny na wykonanie
algorytmu jako funkcja rozmiaru zadania, za jednostkę
przyjmuje się
wykonanie jednej operacji dominującej
.
Złożoność czasowa asymptotyczna
– charakter złożoności
czasowej przy dążeniu do wartości granicznej wraz ze
wzrostem rozmiaru zadania.
Złożoność oczekiwana
– pewna „średnia” złożoność dla
wszystkich możliwych wejść danego rozmiaru.
Złożoność pamięciowa
– pamięć potrzebna do wykonania
algorytmu jako funkcja rozmiaru zadania, za jednostkę
przyjmuje
Opis poleceń maszyny RAM:
LOAD a
– c(0) ← v(
a), co oznacza zapis wartości operandu
a
do rejestru 0 (sumatora),
STORE i
– c(i) ← c(0),
STORE *i –
c(c(i)) ← c(0),
ADD a
– c(0) ← c(0) + v(a),
SUB a
– c(0) ← c(0) – v(a),
MULT a
– c(0) ← c(0) × v(a),
DIV a
– c(0) ← c(0) / v(a),
READ i
– c(i) ←
kolejny symbol wejściowy
,
READ *i
– c(c(i)) ←
kolejny symbol wejściowy
,
WRITE a
– v(a)
jest zapisywane do tej klatki taśmy
wyjściowej, przy której aktualnie znajduje się głowica
,
JUMP b
–
licznik rozkazów jest ustawiany na komendę z
etykietą
b,
JGTZ b
–
jeśli
c(0)
> 0, to licznik rozkazów jest ustawiany na
komendę z etykietą
b
; w przeciwnym razie na komendę
następną
,
JZERO b
–
jeśli
c(0)
= 0, to licznik rozkazów jest ustawiany
na komendę z etykietą
b
; w przeciwnym razie na
komendę następną
,
HALT
–
zatrzymanie programu.
Podstawowe operatory pseudokodu:
Nadawanie wartości:
zmienna ← wyrażenie,
Operator warunkowy:
jeśli
warunek
to
operator(y)
inaczej
operator(y),
Operator pętli „dopóki”:
dopóki
warunek
wykonuj
operator(y),
Operator pętli „powtarzaj”:
powtarzaj
operator(y)
aż_do
warunek,
Operator pętli „dla”:
dla
zmienna ← wartość_początkowa
[w_dół_]do
wartość_końcowa
wykonuj
operator(y).
Wagi logarytmiczne operandów:
=i
– l(i),
i
– l(i) + l(c(i)),
*i
– l(i) + l(c(i)) + l(c(c(i))).
Wagi logarytmiczne komend:
LOAD a
– t(a),
STORE i
– l(c(0)) + l(i),
STORE *i
– l(c(0)) + l(i) + l(c(i)),
ADD a
– l(c(0)) + t(a),
SUB a
– l(c(0)) + t(a),
MULT a
– l(c(0)) + t(a),
DIV a
– l(c(0)) + t(a),
READ i
– l(wejście) + l(i),
READ *i
– l(wejście) + l(i) + l(c(i)),
WRITE a
– t(a),
JUMP b
– 1,
JGTZ b
– l(c(0)),
JZERO b
– l(c(0)),
HALT
– 1.
Lista jednokierunkowa:
się
słowo pamięci maszyny
.
 Lista dwukierunkowa:
Przejście z zapisu infiksowego do zapisu postfiksowego:
Przechodzenie drzewa binarnego metodą
inorder
:
INF-PSF(
TWE
,
LWY
)
01
top[STOS]
←
0
02
head[LWY]
← nil
03
i
←
1
04
powtarzaj
05
jeśli
TWE[i]
jest liczbą
06
to
{
key[x]
← TWE[i]
07 LISTA-WSTAW(
LWY
,
x
) }
08
inaczej
jeśli
TWE[i]
= „+” lub
TWE[i]
= „*”
09
to
PUSH(
STOS
,
TWE[i]
)
10
inaczej
jeśli
TWE[i]
= „)”
11
to
{
key[x]
←
POP(STOS)
12 LISTA-WSTAW(
LWY
,
x
) }
13
i
← i
+ 1
14
aż_do
i
>
length[TWE]
15
jeśli
STOS-PUSTY(
STOS
)
16
to
LISTA-ODWR(
LWY
)
17
inaczej
{
key[x]
←
POP(
STOS
)
18 LISTA-WSTAW(
LWY
,
x
)
19 LISTA-ODWR(
LWY
) }
head[L]
– odwołanie do wskaźnika na początek listy
L
,
prev[x]
– wskaźnik na poprzedni element,
key[x]
– zawartość informacyjna elementu,
next[x]
– wskaźnik na następny element,
nil
– wskaźnik pusty.
1. lewy syn, 2. węzeł, 3. prawy syn.
Poszukiwanie elementu w liście
(czas
O(n)
)
:
DRZB-INORDER(
węzeł
)
1
jeśli
LS[węzeł]
!= 0
2
to
DRZB-INORDER(
LS[węzeł]
)
3 NUMER[
węzeł
]
← licznik
4
licznik
← licznik
+ 1
5
jeśli
RS[węzeł]
!= 0
6
to
DRZB-INORDER(
RS[węzeł]
)
LISTA-POSZ(
L
,
k
)
1
x
← head[L]
2
dopóki
x
!=
nil
i
key[x]
!=
k
3
wykonuj
x
← next[x]
4
zwróć
x
DRZBST-INORDER(
x
)
1
jeśli
x
!=
nil
2
to
{ DRZBST-INORDER(
left[x]
)
3 wypisz
key[x]
4 DRZBST-INORDER(
right[x]
) }
Wstawianie elementu na początek listy
(czas
O(1)
)
:
LISTA-WSTAW(
L
,
x
)
1
next[x]
← head[L]
2
jeśli
head[L]
!=
nil
3
to
prev[head[L]]
← x
4
head[L]
← x
5
prev[x]
← nil
Kolejka:
Przechodzenie drzewa binarnego metodą
postorder
:
Usuwanie elementu z listy
(czas
O(1)
)
:
head[Q]
– indeks elementu znajdującego się na początku
kolejki (głowa),
tail[Q]
– indeks pierwszego wolnego elementu na końcu
kolejki (ogon),
length[Q]
– długość (ilość elementów) kolejki,
head[Q] = tail[Q]
– kolejka jest pusta,
head[Q] = tail[Q] + 1
– kolejka jest pełna.
LISTA-USUŃ(
L
,
x
)
1
jeśli
prev[x]
!=
nil
2
to
next[prev[x]]
← next[x]
3
inaczej
head[L]
← next[x]
4
jeśli
next[x]
!=
nil
5
to
prev[next[x]]
← prev[x]
1. lewy syn, 2. prawy syn, 3. węzeł.
DRZB-POSTORDER(
węzeł
)
1
jeśli
LS[węzeł]
!= 0
2
to
DRZB-POSTORDER(
LS[węzeł]
)
3
jeśli
RS[węzeł]
!= 0
4
to
DRZB-POSTORDER(
RS[węzeł]
)
5 NUMER[
węzeł
]
← licznik
6
licznik
← licznik
+ 1
Umieszczanie elementu
x
w kolejce
Q
(czas
O(1)
)
:
Odwracanie kolejności elementów w liście
L
:
ENQUEUE(
Q
,
x
)
1
Q[tail[Q]]
← x
2
jeśli
tail[Q]
=
length[Q]
3
to
tail[Q]
←
1
4
inaczej
tail[Q]
← tail[Q]
+ 1
LISTA-ODWR(
L
)
1
x
←
head[L]
2
head[LR]
← nil
3
dopóki
x
!=
nil
4
wykonuj
{ LISTA-WSTAW(
LR
,
x
)
5
x
← next[x]
}
6
head[L]
← head[LR]
DRZBST-POSTORDER(
x
)
1
jeśli
x
!=
nil
2
to
{ DRZBST-POSTORDER(
left[x]
)
3 DRZBST-POSTORDER(
right[x]
)
4 wypisz
key[x]
}
Usuwanie elementu z kolejki Q
(czas
O(1)
)
:
DEQUEUE(
Q
)
1
x
← Q[head[Q]]
2
jeśli
head[Q]
=
length[Q]
3
to
head[Q]
←
1
4
inaczej
head[Q]
← head[Q]
+ 1
5
zwróć
x
Stos:
Węzeł drzewa binarnego jako struktura ze wskaźnikami:
key[x]
– część informacyjna węzła,
p[x]
– wskaźnik do węzła rodzica,
left[x]
– wskaźnik do lewego syna,
right[x]
– wskaźnik do prawego syna,
p[x] = nil
– węzeł jest korzeniem (
root[T]
),
left[x] = nil
lub
right[x] = nil
– węzeł
x
nie ma lewego lub
prawego syna,
root[T] = nil
– drzewo jest puste.
Przechodzenie drzewa binarnego metoda
preorder
:
S[1..n]
– tablica jednowymiarowa, reprezentująca stos w
pamięci,
top[S]
– atrybut podający numer (indeks) elementu
ostatnio umieszczonego na stosie.
Węzeł drzewa dowolnego jako struktura ze wskaźnikami:
Sprawdzanie, czy stos jest pusty:
p[x]
– wskaźnik na węzeł-rodzic,
key[x]
– zawartość informacyjna węzła,
leftchild[x]
– wskaźnik na węzeł-syn położony najbardziej z
lewej,
rightsibling[x]
– wskaźnik na prawego „brata”, tj. prawy
sąsiedni węzeł będący synem tego samego węzła-
rodzica,
leftchild[x] = nil
– węzeł
x
nie ma synów,
rightsibling[x] = nil
– węzeł jest najbardziej na prawo
położonym synem węzła
x
.
1. węzeł, 2. lewy syn, 3. prawy syn.
STOS-PUSTY(
S
)
1
jeśli
top[S]
= 0
2
to
TRUE
3
inaczej
FALSE
DRZB-PREORDER(
węzeł
)
1 NUMER[
węzeł
]
← licznik
2
licznik
← licznik
+ 1
3
jeśli
LS[węzeł]
!= 0
4
to
DRZB-PREORDER(
LS[węzeł]
)
5
jeśli
RS[węzeł]
!= 0
6
to
DRZB-PREORDER(
RS[węzeł]
)
Umieszczanie elementu
x
na stosie
S
:
PUSH(
S
,
x
)
1
top[S]
← top[S]
+ 1
2
S[top[S]]
← x
DRZBST-PREORDER(
x
)
1
jeśli
x
!=
nil
2
to
{ wypisz
key[x]
3
DRZBST-PREORDER(
left[x]
)
4 DRZBST-PREORDER(
right[x]
) }
Przeszukiwanie w drzewach BST:
BST-POSZ(
x
,
k
)
1
jeśli
x
=
nil
lub
k
=
key[x]
2
to
zwróć
x
3
jeśli
k
<
key[x]
4
to
zwróć
BST-POSZ(
left[x]
,
k
)
5
inaczej
zwróć
BST-POSZ(
right[x]
,
k
)
Zdejmowanie elementu
x
ze stosu
S
:
POP(
S
)
1
jeśli
STOS-PUSTY(
S
)
2
to
błąd „niedomiar”
3
inaczej
{
top[S]
← top[S] –
1
4
zwróć
S[top[S]
+ 1
]
}
 BST-POSZ-ITER(
x
,
k
)
1
dopóki
x
!=
nil
i
k
!=
key[x]
2
wykonuj
jeśli
k
<
key[x]
3
to
x
← left[x]
4
inaczej
x
← right[x]
5
zwróć
x
Reprezentowanie kopca przy pomocy drzewa binarnego:
DRZEWO-WSZERZ(
W1
,
W2
)
01
do_sprawdzenia
←
nil
02 SYNOWIE(
W1
,
do_sprawdzenia
)
03
dopóki
do_sprawdzenia
!=
nil
04
wykonuj
{
pierwszy
← PIERWSZY(
do_sprawdzenia
)
05
jeśli
key[pierwszy]
=
key[W2]
06
to
zwróć
W2
07 SYNOWIE(
pierwszy
,
nowe_węzły
)
08 RESZTA(
do_sprawdzenia
)
09 NOWE-NA-KONIEC(
do_sprawdzenia
,
nowe_węzły
) }
10 wypisz „
węzła nie znaleziono
”
Poszukiwanie węzła o minimalnym i maksymalnym
kluczu w drzewie BST
(czas
O(h)
, gdzie
h
to wysokość
drzewa)
:
BST-MIN(
x
)
1
dopóki
left[x]
!=
nil
2
wykonuj
x
← left[x]
3
zwróć
x
DRZEWO-W-GŁĄB(
W1
,
W2
)
01
do_sprawdzenia
←
nil
02 SYNOWIE(
W1
,
do_sprawdzenia
)
03
dopóki
do_sprawdzenia
!=
nil
04
wykonuj
{
pierwszy
← PIERWSZY(
do_sprawdzenia
)
05
jeśli
key[pierwszy]
=
key[W2]
06
to
zwróć
W2
07 SYNOWIE(
pierwszy
,
nowe_węzły
)
08 RESZTA(
do_sprawdzenia
)
09
length[A]
– liczba elementów w A,
heap-size[A]
– liczba elementów kopca,
A[1]
– korzeń drzewa,
heap-size[A] ≤ length[A]
.
BST-MAX(
x
)
1
dopóki
right[x]
!=
nil
2
wykonuj
x
← right[x]
3
zwróć
x
Obliczanie indeksu rodzica oraz lewego i prawego syna w
kopcu:
NOWE-NA-
POCZĄTEK(
do_sprawdzenia
,
nowe_węzły
) }
10 wypisz „
węzła nie znaleziono
”
PARENT(
i
)
1
zwróć
(
i
/2)
Następniki i poprzedniki w drzewie BST:
BST-NAST(
x
)
1
jeśli
right[x]
!=
nil
2
to
zwróć
BST-MIN(
right[x]
)
3
y
← p[x]
4
dopóki
x
!=
nil
i
x
=
right[y]
5
wykonuj
{
x
← y
6
y
← p[y]
}
7
zwróć
y
LEFT(
i
)
1
zwróć
2
i
Sortowanie przez wstawianie:
SORT-WSTAW(
A
)
1
dla
j
← 2
do
length[A]
2
wykonuj
{
key
←
A[j]
3
i
←
j
– 1
4
dopóki
i
> 0 i
A[i]
>
key
5
wykonuj
{
A[i
+ 1
]
←
A[i]
6
i
←
i
– 1 }
7
A[i
+ 1
]
←
key
}
RIGHT(
i
)
1
zwróć
2
i
+1
Przywracanie własności kopca:
BST-POPRZ(
x
)
1
jeśli
left[x]
!=
nil
2
to
zwróć
BST-MAX(
left[x]
)
3
y
← p[x]
4
dopóki
x
!=
nil
i
x
=
left[y]
5
wykonuj
{
x
← y
6
y
← p[y]
}
7
zwróć
y
KOPIEC-PRZYWR(
A
,
i
)
01
l
← LEFT(
i
)
02
r
← RIGHT(
i
)
03
jeśli
l
≤
heap-size[A]
i
A[l]
>
A[i]
04
to
największy
←
l
05
inaczej
największy
←
i
06
jeśli
r
≤
heap-size[A]
i
A[r]
>
A[największy]
07
to
największy
←
r
08
jeśli
największy
!=
i
09
to
{ zamień
A[i]
↔
A[największy]
10 KOPIEC-PRZYWR(
A
,
największy
) }
Sortowanie przez kopcowanie (
heapsort
):
SORT-KOPCOW(
A
)
1 KOPIEC-BUDUJ(
A
)
2
dla
i
←
length[A]
w_dół_do
2
3
wykonuj
{ zamień
A[1]
↔
A[i]
4
heap-size[A]
←
heap-size[A]
– 1
5 KOPIEC-PRZYWR(
A
,1) }
Operacje wstawiania i usuwania w drzewie BST:
BST-WSTAW(
T
,
z
)
01
y
← nil
02
x
← root[T]
03
dopóki
x
!=
nil
04
wykonuj
{
y
← x
05
jeśli
key[z]
<
key[x]
06
to
x
← left[x]
07
inaczej
x
← right[x]
}
08
p[z]
← y
09
jeśli
y
=
nil
10
to
root[T]
← z
11
inaczej
jeśli
key[z]
<
key[y]
12
to
left[y]
← z
13
inaczej
right[y]
← z
Budowanie kopca:
Sortowanie przez zliczanie:
KOPIEC-BUDUJ(
A
)
1
heap-size[A]
←
length[A]
2
dla
i
← (
length[A]
/2)
w_dół_do
1
3
wykonuj
KOPIEC-PRZYWR(
A
,
i
)
SORT-ZLICZANIE(
A
,
B
,
k
)
1
dla
i
← 1
do
k
2
wykonuj
C[i]
← 0
3
dla
j
← 1
do
length[A]
4
wykonuj
C[A[j]]
←
C[A[j]]
+ 1
5
dla
i
← 2
do
k
6
wykonuj
C[i]
←
C[i]
+
C[i
– 1
]
7
dla
j
←
length[A]
w_dół_do
1
8
wykonuj
{
B[C[A[j]]]
←
A[j]
9
C[A[j]]
←
C[A[j]]
– 1 }
Usuwanie maksymalnego elementu z kolejki
priorytetowej:
KOPIEC-USUŃ-MAX(
A
)
1
jeśli
heap-size[A]
< 1
2
to
błąd „
kopiec pusty
”
3
max
←
A[1]
4
A[1]
←
A[heap-size[A]]
5
heap-size[A]
←
heap-size[A]
– 1
6 KOPIEC-PRZYWR(
A
,1)
7
zwróć
max
BST-USUN(
T
,
z
)
01
jeśli
left[z]
=
nil
lub
right[z]
=
nil
02
to
y
← z
03
inaczej
y
←
BST-NAST(
z
)
04
jeśli
left[y]
!=
nil
05
to
x
← left[y]
06
inaczej
x
← right[y]
07
jeśli
x
!=
nil
08
to
p[x]
← p[y]
09
jeśli
p[y]
=
nil
10
to
root[T]
← x
11
inaczej
jeśli
y
=
left[p[y]]
12
to
left[p[y]]
← x
13
inaczej
right[p[y]]
← x
14
jeśli
y
!=
z
15
to
key[z]
← key[y]
Sortowanie kubełkowe:
SORT-KUBEŁKOWE(A)
1 n ← length[A]
2 dla i ← 1 do n
3 wykonuj wstaw A[i] do listy B[(n A[i])]
4 dla i ← 0 do n – 1
5 wykonuj { posortuj listę B[i] przez wstawianie
6 połącz listy B[0], B[1], ..., B[n – 1] w tej kolejności
Dodawanie nowego elementu do kolejki priorytetowej
(czas
O(
lg
n)
)
:
KOPIEC-WSTAW(
A
,
key
)
1
heap-size[A]
←
heap-size[A]
+ 1
2
i
←
heap-size[A]
3
dopóki
i
> 1 i
A[
PARENT(
i
)
]
<
key
4
wykonuj
{
A[i]
←
A[
PARENT(
i
)
]
5
i
← PARENT(
i
) }
6
A[i]
←
key
Przeglądanie dowolnego drzewa wszerz i w głąb:
SYNOWIE(
w
,
lista_s
) – dla węzła w generuje listę lista_s
węzłów-synów tego węzła,
PIERWSZY(
lista_w
) – dla niepustej listy węzłów
lista_w
zwraca wskaźnik na pierwszy węzeł,
RESZTA(
lista_w
) – w liście węzłów
lista_w
usuwa pierwszy
węzeł,
NOWE-NA-KONIEC(
lista_w1
,
lista_w2
) – na koniec listy
węzłów
lista_w1
dodaje listę węzłów
lista_w2
.
  [ Pobierz całość w formacie PDF ]