Kopiec, wykorzystanie do Dijkstry
II kurs, 2. zaj ˛ecia
Marcin Andrychowicz
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
O(n)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
O(n)
posortowana tablica
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
O(n)
posortowana tablica
O(n)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
O(n)
posortowana tablica
O(n)
O(n)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
O(n)
posortowana tablica
O(n)
O(n)
O(1)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Wst ˛ep
Porównanie zło˙zono´sci
wstawienie
usuni ˛ecie
minimum
tablica
O(1)
O(1)
O(n)
posortowana tablica
O(n)
O(n)
O(1)
kopiec
O(log n)
O(log n)
O(log n)
wstawienie — wstawienie elementu
usuni ˛ecie — usuni ˛ecie elementu na podanej pozycji (a
nie o danej warto´sci)
minimum — znalezienie minimum
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
wyja´snienie nazwy:
binarne — ka˙zdy wierzchołek ma co najwy˙zej 2 synów
pełne — li´scie znajduj ˛
a si ˛e tylko na 2 poziomach przy
czym te na ni˙zszym poziomie s ˛
a „z jednej strony”
wierzchołki numerujemy jak na rysunku
w wierzchołkach b ˛edziemy trzymali liczby
heap[i]
— warto´s´c w i-tym wierzchołku
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
wyja´snienie nazwy:
binarne — ka˙zdy wierzchołek ma co najwy˙zej 2 synów
pełne — li´scie znajduj ˛
a si ˛e tylko na 2 poziomach przy
czym te na ni˙zszym poziomie s ˛
a „z jednej strony”
wierzchołki numerujemy jak na rysunku
w wierzchołkach b ˛edziemy trzymali liczby
heap[i]
— warto´s´c w i-tym wierzchołku
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
wyja´snienie nazwy:
binarne — ka˙zdy wierzchołek ma co najwy˙zej 2 synów
pełne — li´scie znajduj ˛
a si ˛e tylko na 2 poziomach przy
czym te na ni˙zszym poziomie s ˛
a „z jednej strony”
wierzchołki numerujemy jak na rysunku
w wierzchołkach b ˛edziemy trzymali liczby
heap[i]
— warto´s´c w i-tym wierzchołku
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
wyja´snienie nazwy:
binarne — ka˙zdy wierzchołek ma co najwy˙zej 2 synów
pełne — li´scie znajduj ˛
a si ˛e tylko na 2 poziomach przy
czym te na ni˙zszym poziomie s ˛
a „z jednej strony”
wierzchołki numerujemy jak na rysunku
w wierzchołkach b ˛edziemy trzymali liczby
heap[i]
— warto´s´c w i-tym wierzchołku
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
wyja´snienie nazwy:
binarne — ka˙zdy wierzchołek ma co najwy˙zej 2 synów
pełne — li´scie znajduj ˛
a si ˛e tylko na 2 poziomach przy
czym te na ni˙zszym poziomie s ˛
a „z jednej strony”
wierzchołki numerujemy jak na rysunku
w wierzchołkach b ˛edziemy trzymali liczby
heap[i]
— warto´s´c w i-tym wierzchołku
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
Dlaczego taka numeracja jest wygodna?
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to bx /2c
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
Dlaczego taka numeracja jest wygodna?
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to bx /2c
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
Dlaczego taka numeracja jest wygodna?
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to bx /2c
Pełne drzewo binarne
Pełne drzewo binarne
1
2
3
4
5
6
7
8
9
10
11
12
Dlaczego taka numeracja jest wygodna?
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to bx /2c
Kopiec
Kopiec
2
3
5
3
6
7
6
8
4
9
8
7
Własno´s´c kopca
Kopcem
nazywamy pełne drzewo binarne, które posiada
własno´s´c kopca, tzn. ka˙zdy wierzchołek ma przypisan ˛
a
warto´s´c nie wi ˛eksz ˛
a ni˙z jego synowie.
Innymi słowy, dla wszystkich x zachodzi
heap[bx /2c] ¬ heap[x ].
Dodawanie elementu
Kopiec
2
3
5
3
6
7
6
8
4
9
8
7
Jak doda´c element do kopca?
1
dodajemy element na koniec tablicy (własno´s´c kopca
mo˙ze by´c zaburzona)
2
dopóki ojciec nowego elementu jest od niego wi ˛ekszy,
to zamieniamy warto´sci w obu wierzchołkach
Dodawanie elementu
Kopiec
2
3
5
3
6
7
6
8
4
9
8
7
4
Jak doda´c element do kopca?
1
dodajemy element na koniec tablicy (własno´s´c kopca
mo˙ze by´c zaburzona)
2
dopóki ojciec nowego elementu jest od niego wi ˛ekszy,
to zamieniamy warto´sci w obu wierzchołkach
Dodawanie elementu
Kopiec
2
3
5
3
6
7
6
8
4
9
8
7
4
Jak doda´c element do kopca?
1
dodajemy element na koniec tablicy (własno´s´c kopca
mo˙ze by´c zaburzona)
2
dopóki ojciec nowego elementu jest od niego wi ˛ekszy,
to zamieniamy warto´sci w obu wierzchołkach
Dodawanie elementu
Kopiec
2
3
5
3
6
4
6
8
4
9
8
7
7
Jak doda´c element do kopca?
1
dodajemy element na koniec tablicy (własno´s´c kopca
mo˙ze by´c zaburzona)
2
dopóki ojciec nowego elementu jest od niego wi ˛ekszy,
to zamieniamy warto´sci w obu wierzchołkach
Dodawanie elementu
Kopiec
2
3
5
3
6
4
6
8
4
9
8
7
7
Jak doda´c element do kopca?
1
dodajemy element na koniec tablicy (własno´s´c kopca
mo˙ze by´c zaburzona)
2
dopóki ojciec nowego elementu jest od niego wi ˛ekszy,
to zamieniamy warto´sci w obu wierzchołkach
Dodawanie elementu
Kopiec
2
3
4
3
6
5
6
8
4
9
8
7
7
Jak doda´c element do kopca?
1
dodajemy element na koniec tablicy (własno´s´c kopca
mo˙ze by´c zaburzona)
2
dopóki ojciec nowego elementu jest od niego wi ˛ekszy,
to zamieniamy warto´sci w obu wierzchołkach
Jak doda´c element do kopca?
HeapUp
Proces przenoszenia elementu kopca coraz wy˙zej w celu
przywrócenia własno´sci kopca nazywamy kopcowaniem w
gór˛
e (HeapUp)
. W notatkach znajduje si ˛e implementacja
wstawiania elementu do kopca.
Szukanie minimum
Kopiec
2
3
5
3
6
7
6
8
4
9
8
7
Jak znale´z´c minimum w kopcu?
Minimum znajduje si ˛e oczywi´scie z korzeniu, czyli w
heap[1].
Usuwanie korzenia
Kopiec
2
3
5
3
6
7
6
8
4
9
8
7
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
7
3
5
3
6
7
6
8
4
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
7
3
5
3
6
7
6
8
4
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
3
7
5
3
6
7
6
8
4
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
3
7
5
3
6
7
6
8
4
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
3
3
5
7
6
7
6
8
4
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
3
3
5
7
6
7
6
8
4
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Usuwanie korzenia
Kopiec
3
3
5
4
6
7
6
8
7
9
8
Jak usun ˛
a´c korze ´n?
1
w miejsce korzenia wstawiamy ostatni element
(własno´s´c kopca mo˙ze by´c zaburzona)
2
dopóki wstawiony element jest wi ˛ekszy od którego´s ze
swoich synów to zamieniamy go z synem o mniejszej
warto´sci
Jak usun ˛
a´c korze ´n?
HeapDown
Proces przenoszenia elementu kopca coraz ni˙zej w celu
przywrócenia własno´sci kopca nazywamy kopcowaniem w
dół (HeapDown)
. W notatkach znajduje si ˛e
implementacja usuwania korzenia z kopca.
Usuwanie dowolnego elementu
Problem
W jaki sposób mo˙zemy usun ˛
a´c element na danej pozycji
(niekoniecznie korze ´n)?
Rozwi ˛
azanie
Post ˛
apimy podobnie jak w przypadku korzenia:
1
w miejsce usuwanego elementu wstawiamy ostatni
element
2
kopcujemy nowy element w gór ˛e
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Problem
W jaki sposób mo˙zemy usun ˛
a´c element na danej pozycji
(niekoniecznie korze ´n)?
Rozwi ˛
azanie
Post ˛
apimy podobnie jak w przypadku korzenia:
1
w miejsce usuwanego elementu wstawiamy ostatni
element
2
kopcujemy nowy element w gór ˛e
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Problem
W jaki sposób mo˙zemy usun ˛
a´c element na danej pozycji
(niekoniecznie korze ´n)?
Rozwi ˛
azanie
Post ˛
apimy podobnie jak w przypadku korzenia:
1
w miejsce usuwanego elementu wstawiamy ostatni
element
2
kopcujemy nowy element w gór ˛e
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Problem
W jaki sposób mo˙zemy usun ˛
a´c element na danej pozycji
(niekoniecznie korze ´n)?
Rozwi ˛
azanie
Post ˛
apimy podobnie jak w przypadku korzenia:
1
w miejsce usuwanego elementu wstawiamy ostatni
element
2
kopcujemy nowy element w gór ˛e
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Problem
W jaki sposób mo˙zemy usun ˛
a´c element na danej pozycji
(niekoniecznie korze ´n)?
Rozwi ˛
azanie
Post ˛
apimy podobnie jak w przypadku korzenia:
1
w miejsce usuwanego elementu wstawiamy ostatni
element
2
kopcujemy nowy element w gór ˛e
3
kopcujemy nowy element w dół
Analiza zło˙zono´sci
Analiza zło˙zono´sci
Wszystkie opisane operacje działaj ˛
a w czasie
proporcjonalnym do wysoko´sci kopca, która jest
logarytmiczna wzgl ˛edem ilo´sci elementów w kopcu.
Sortowanie przez kopcowanie (heapsort)
Problem
Jak mo˙zna wykorzysta´c kopiec do uzyskania szybkiego —
O(n log n) algorytmu sortowania?
Rozwi ˛
azanie
Elementy tablicy, któr ˛
a chcemy posortowa´c wrzucamy do
kopca a nast ˛epnie dopóki kopiec nie jest pusty, to
wypisujemy minimum i je usuwamy.
Sortowanie przez kopcowanie (heapsort)
Problem
Jak mo˙zna wykorzysta´c kopiec do uzyskania szybkiego —
O(n log n) algorytmu sortowania?
Rozwi ˛
azanie
Elementy tablicy, któr ˛
a chcemy posortowa´c wrzucamy do
kopca a nast ˛epnie dopóki kopiec nie jest pusty, to
wypisujemy minimum i je usuwamy.
Kopiec a algorytm Dijkstry
Inne zastosowanie kopca
Jednym z najcz ˛e´sciej spotykanych zastosowa ´n kopca jest
u˙zycie go do przyspieszenia algorytmu Dijkstry. Na
pocz ˛
atku przypomnimy ten algorytm.
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Algorytm Dijkstry
1
oznacz wszystkie wierzchołki jako nieodwiedzone
2
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
3
ustaw dis[s] = 0
4
dopóki istnieje nieodwiedzony wierzchołek o
sko ´nczonej odległo´sci:
1
niech v b ˛edzie wierzchołkiem nieodwiedzonym o
najmniejszej odległo´sci
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v
w ˛
askie gardło: t ˛
a operacj ˛e wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Jak to przyspieszy´c?
chcieliby´smy trzyma´c w kopcu wierzchołki
nieodwiedzone i móc szybko wyci ˛
aga´c z niego
wierzchołek x o najmniejszej warto´sci dis[x ]
mo˙zemy trzyma´c w kopcu numery wierzchołków grafu
przy kopcowaniu musimy wówczas porównywa´c
odpowiednie warto´sci w tablicy dis a nie bezpo´srednio
warto´sci trzymane w kopcu (dis[x ] b ˛edziemy nazywa´c
priorytetem warto´sci x )
problem: priorytety mog ˛
a ulega´c zmianie (ale tylko
male´c), co mo˙ze zaburzy´c własno´s´c kopca
Kopiec a algorytm Dijkstry
Jak to przyspieszy´c?
chcieliby´smy trzyma´c w kopcu wierzchołki
nieodwiedzone i móc szybko wyci ˛
aga´c z niego
wierzchołek x o najmniejszej warto´sci dis[x ]
mo˙zemy trzyma´c w kopcu numery wierzchołków grafu
przy kopcowaniu musimy wówczas porównywa´c
odpowiednie warto´sci w tablicy dis a nie bezpo´srednio
warto´sci trzymane w kopcu (dis[x ] b ˛edziemy nazywa´c
priorytetem warto´sci x )
problem: priorytety mog ˛
a ulega´c zmianie (ale tylko
male´c), co mo˙ze zaburzy´c własno´s´c kopca
Kopiec a algorytm Dijkstry
Jak to przyspieszy´c?
chcieliby´smy trzyma´c w kopcu wierzchołki
nieodwiedzone i móc szybko wyci ˛
aga´c z niego
wierzchołek x o najmniejszej warto´sci dis[x ]
mo˙zemy trzyma´c w kopcu numery wierzchołków grafu
przy kopcowaniu musimy wówczas porównywa´c
odpowiednie warto´sci w tablicy dis a nie bezpo´srednio
warto´sci trzymane w kopcu (dis[x ] b ˛edziemy nazywa´c
priorytetem warto´sci x )
problem: priorytety mog ˛
a ulega´c zmianie (ale tylko
male´c), co mo˙ze zaburzy´c własno´s´c kopca
Kopiec a algorytm Dijkstry
Jak to przyspieszy´c?
chcieliby´smy trzyma´c w kopcu wierzchołki
nieodwiedzone i móc szybko wyci ˛
aga´c z niego
wierzchołek x o najmniejszej warto´sci dis[x ]
mo˙zemy trzyma´c w kopcu numery wierzchołków grafu
przy kopcowaniu musimy wówczas porównywa´c
odpowiednie warto´sci w tablicy dis a nie bezpo´srednio
warto´sci trzymane w kopcu (dis[x ] b ˛edziemy nazywa´c
priorytetem warto´sci x )
problem: priorytety mog ˛
a ulega´c zmianie (ale tylko
male´c), co mo˙ze zaburzy´c własno´s´c kopca
Jak znale´z´c element w kopcu?
Problem
Za ka˙zdym razem, gdy priorytet jakiego´s elementu si ˛e
zmniejszy musimy wykona´c kopcowanie tego elementu w
gór ˛e. Umiemy jednak wykonywa´c kopcowanie jedynie
elementu na danej pozycji (a nie o danej warto´sci). Jak
rozwi ˛
aza´c ten problem?
Rozwi ˛
azanie
Oprócz tablicy heap, b ˛edziemy trzymali tablic ˛e where, gdzie
where[x ] oznacza pozycj ˛e w kopcu warto´sci x , tzn.
heap[where[x ]] = x . Przyjmujemy where[x ] = 0, je´sli w
kopcu nie ma elementu x . Tablic ˛e t ˛e musimy uaktualnia´c za
ka˙zdym razem, gdy przemieszczamy elementy w kopcu.
Jak znale´z´c element w kopcu?
Problem
Za ka˙zdym razem, gdy priorytet jakiego´s elementu si ˛e
zmniejszy musimy wykona´c kopcowanie tego elementu w
gór ˛e. Umiemy jednak wykonywa´c kopcowanie jedynie
elementu na danej pozycji (a nie o danej warto´sci). Jak
rozwi ˛
aza´c ten problem?
Rozwi ˛
azanie
Oprócz tablicy heap, b ˛edziemy trzymali tablic ˛e where, gdzie
where[x ] oznacza pozycj ˛e w kopcu warto´sci x , tzn.
heap[where[x ]] = x . Przyjmujemy where[x ] = 0, je´sli w
kopcu nie ma elementu x . Tablic ˛e t ˛e musimy uaktualnia´c za
ka˙zdym razem, gdy przemieszczamy elementy w kopcu.
Algorytm Dijkstry z kopcem
Analiza zło˙zono´sci
nieodwiedzony wierzchołek o najmniejszej odległo´sci
mo˙zemy znale´z´c teraz w czasie O(log |V |)
relaksacja kraw ˛edzi zajmuje teraz czas O(log |V |), wi ˛ec
relaksacja wszystkich kraw ˛edzi zajmuje czas
O(|E | log |V |) i taka te˙z jest zło˙zono´s´c całego algorytmu
Algorytm Dijkstry z kopcem
Analiza zło˙zono´sci
nieodwiedzony wierzchołek o najmniejszej odległo´sci
mo˙zemy znale´z´c teraz w czasie O(log |V |)
relaksacja kraw ˛edzi zajmuje teraz czas O(log |V |), wi ˛ec
relaksacja wszystkich kraw ˛edzi zajmuje czas
O(|E | log |V |) i taka te˙z jest zło˙zono´s´c całego algorytmu
Wady takiego rozwi ˛
azania
Wady:
musimy zaimplementowa´c kopiec z operacj ˛
a zmiany
priorytetu, co mo˙ze zaj ˛
a´c do´s´c du˙zo czasu
gotowe implementacje kopca, o których dowiesz si ˛e na
jednych z nast ˛epnych zaj ˛e´c, nie posiadaj ˛
a tej operacji
Wady takiego rozwi ˛
azania
Wady:
musimy zaimplementowa´c kopiec z operacj ˛
a zmiany
priorytetu, co mo˙ze zaj ˛
a´c do´s´c du˙zo czasu
gotowe implementacje kopca, o których dowiesz si ˛e na
jednych z nast ˛epnych zaj ˛e´c, nie posiadaj ˛
a tej operacji
Inne rozwi ˛
azanie
Inne rozwi ˛
azanie
przedstawimy teraz rozwi ˛
azanie, które korzysta ze
zwykłego kopca (bez operacji zmiany priorytetu)
do kopca b ˛edziemy wrzuca´c pary (dis[x ], x )
przyjmujemy porz ˛
adek leksykograficzny na parach, tzn.
(
x , y ) < (a, b) wtw. x < a ∨ (x = a ∧ y < b)
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległo´sci
Inne rozwi ˛
azanie
Inne rozwi ˛
azanie
przedstawimy teraz rozwi ˛
azanie, które korzysta ze
zwykłego kopca (bez operacji zmiany priorytetu)
do kopca b ˛edziemy wrzuca´c pary (dis[x ], x )
przyjmujemy porz ˛
adek leksykograficzny na parach, tzn.
(
x , y ) < (a, b) wtw. x < a ∨ (x = a ∧ y < b)
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległo´sci
Inne rozwi ˛
azanie
Inne rozwi ˛
azanie
przedstawimy teraz rozwi ˛
azanie, które korzysta ze
zwykłego kopca (bez operacji zmiany priorytetu)
do kopca b ˛edziemy wrzuca´c pary (dis[x ], x )
przyjmujemy porz ˛
adek leksykograficzny na parach, tzn.
(
x , y ) < (a, b) wtw. x < a ∨ (x = a ∧ y < b)
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległo´sci
Inne rozwi ˛
azanie
Inne rozwi ˛
azanie
przedstawimy teraz rozwi ˛
azanie, które korzysta ze
zwykłego kopca (bez operacji zmiany priorytetu)
do kopca b ˛edziemy wrzuca´c pary (dis[x ], x )
przyjmujemy porz ˛
adek leksykograficzny na parach, tzn.
(
x , y ) < (a, b) wtw. x < a ∨ (x = a ∧ y < b)
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległo´sci
Problem zmiany priorytetu
Problem
Co zrobi´c je´sli warto´s´c dis[x ] si ˛e zmieni?
Rozwi ˛
azanie
Wrzucamy do kopca now ˛
a par ˛e (dis[x ], x ). Przy takim
podej´sciu w kopcu b ˛ed ˛
a znajdowały si ˛e ´smieci —
nieaktualne pary postaci (d , x ), gdzie d > dis[x ]. Pary takie
po prostu pomijamy przy wyci ˛
aganiu ich z kopca.
Problem zmiany priorytetu
Problem
Co zrobi´c je´sli warto´s´c dis[x ] si ˛e zmieni?
Rozwi ˛
azanie
Wrzucamy do kopca now ˛
a par ˛e (dis[x ], x ). Przy takim
podej´sciu w kopcu b ˛ed ˛
a znajdowały si ˛e ´smieci —
nieaktualne pary postaci (d , x ), gdzie d > dis[x ]. Pary takie
po prostu pomijamy przy wyci ˛
aganiu ich z kopca.
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Nowa wersja algorytmu Dijkstry
Algorytm Dijkstry z kopcem:
1
dla ka˙zdego v ∈ V ustaw dis[v ] = ∞
2
ustaw dis[s] = 0
3
wrzu´c do kopca par ˛e (0, s)
4
dopóki kopiec nie jest pusty
1
wyci ˛
agnij najmniejsz ˛
a par ˛e z kopca, oznaczmy j ˛
a (d , v )
2
je´sli d > dis[v ] to powró´c do pkt. 4
3
zrelaksuj wszystkie kraw ˛edzie wychodz ˛
ace z v , je´sli
poprawia to odległo´s´c do wierzchołka x , to wrzu´c par ˛e
(
dis[x ], x ) do kopca
Analiza algorytmu
Analiza algorytmu
w tym przypadku rozmiar kopca wynosi O(|E |) a nie
O(|V |)
nie wpływa to jednak na zło˙zono´s´c, gdy˙z wynosi ona
O(|E | log |E |) = O(|E | log |V |
2
) =
O(2|E | log |V |) =
O(|E | log |V |)
jest on nieznacznie prostszy w implementacji ni˙z
poprzedni
nie wymaga kopca z operacj ˛
a zmiany priorytetu
Analiza algorytmu
Analiza algorytmu
w tym przypadku rozmiar kopca wynosi O(|E |) a nie
O(|V |)
nie wpływa to jednak na zło˙zono´s´c, gdy˙z wynosi ona
O(|E | log |E |) = O(|E | log |V |
2
) =
O(2|E | log |V |) =
O(|E | log |V |)
jest on nieznacznie prostszy w implementacji ni˙z
poprzedni
nie wymaga kopca z operacj ˛
a zmiany priorytetu
Analiza algorytmu
Analiza algorytmu
w tym przypadku rozmiar kopca wynosi O(|E |) a nie
O(|V |)
nie wpływa to jednak na zło˙zono´s´c, gdy˙z wynosi ona
O(|E | log |E |) = O(|E | log |V |
2
) =
O(2|E | log |V |) =
O(|E | log |V |)
jest on nieznacznie prostszy w implementacji ni˙z
poprzedni
nie wymaga kopca z operacj ˛
a zmiany priorytetu
Analiza algorytmu
Analiza algorytmu
w tym przypadku rozmiar kopca wynosi O(|E |) a nie
O(|V |)
nie wpływa to jednak na zło˙zono´s´c, gdy˙z wynosi ona
O(|E | log |E |) = O(|E | log |V |
2
) =
O(2|E | log |V |) =
O(|E | log |V |)
jest on nieznacznie prostszy w implementacji ni˙z
poprzedni
nie wymaga kopca z operacj ˛
a zmiany priorytetu
Document Outline
Wyszukiwarka
Podobne podstrony:
Elementy statystyki matematycznej wykorzystywane do opracowywania wielkości wyznaczanych, Geodezja i
diatermia, Diatermia kondensatorowa wykorzystuje do nagrzania tkanek pole elektryczne
Zestawienie wazniejszych cech uzytkowych urzadzen wykorzystywanych do odzysku ciepla, Pomoce naukowe
21-25, tablice, Potrafisz już przechowywać w programie liczby całkowite, rzeczywiste, znaki i napisy
projekty elektryczne, wylzm, Przedstawiony w artykule wyłącznik zmierzchowy można wykorzystać do zał
Dowody księgowe do wykorzystania, do Szkoły, matura, praca mgr i podyplom., encyklopedie, ściągi, Ek
J Kossecki, O pewnych stereotypach wykorzystywanych do działań dezinformacyjnych i dezintegracyjnych
Bombka choinkowa z recyklingu Niepotrzebne płyty? możemy wykorzystać do wykonania bombek choinkowy
Wykorzystane do wspomagania działalności żydowskiego lobby w Polsce, Polska
BADANIA KOROZYJNE ALUMINIOWYCH KOMPOZYTÓW ZBROJONYCH SIC WYKORZYSTYWANYCH DO PRODUKCJI TARCZ HAMULCO
TECHNIKI CHROMATOGRAFICZNE WYKORZYSTYWANE DO ROZDZIAŁU BIAŁEK
USTAWA z dnia 10 marca 2006 r o zwrocie podatku akcyzowego zawartego w cenie oleju napędowego wykorz
Wełny wykorzystywane do filcowania
Narzedzia wykorzystywane do potrzeb promocji zdrowia i profilaktyki[1](1)
Wzor 14 Ankieta dotyczaca komputerow i urzadzen mobilnych wykorzystywanych do przetwarzania danych
Test Wingate jest jednym z najbardziej wiarygodnych testów wykorzystywanych do oceny wydolności bezt
Wzor 15 Ankieta dotyczaca aplikacji wykorzystywanych do przetwarzania danych
więcej podobnych podstron