Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Kopiec, wykorzystanie do Dijkstry
Własność kopca
dodawanie
minimum
II kurs, 2. zajęcia
usuwanie
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
bez zmiany
priorytetu
Marcin Andrychowicz
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
Tablica
wstawienie usunięcie minimum
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności
heapsort
Dijkstra
wstawienie  wstawienie elementu
zastosowanie Kopca
zmiana priorytetu
bez zmiany
usunięcie  usunięcie elementu na podanej pozycji (a
priorytetu
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
Tablica
wstawienie usunięcie minimum
Własność kopca
dodawanie
tablica
minimum
usuwanie
analiza złożoności
heapsort
Dijkstra
wstawienie  wstawienie elementu
zastosowanie Kopca
zmiana priorytetu
bez zmiany
usunięcie  usunięcie elementu na podanej pozycji (a
priorytetu
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
Tablica
wstawienie usunięcie minimum
Własność kopca
dodawanie
tablica O(1)
minimum
usuwanie
analiza złożoności
heapsort
Dijkstra
wstawienie  wstawienie elementu
zastosowanie Kopca
zmiana priorytetu
bez zmiany
usunięcie  usunięcie elementu na podanej pozycji (a
priorytetu
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
Tablica
wstawienie usunięcie minimum
Własność kopca
dodawanie
tablica O(1) O(1)
minimum
usuwanie
analiza złożoności
heapsort
Dijkstra
wstawienie  wstawienie elementu
zastosowanie Kopca
zmiana priorytetu
bez zmiany
usunięcie  usunięcie elementu na podanej pozycji (a
priorytetu
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
Tablica
wstawienie usunięcie minimum
Własność kopca
dodawanie
tablica O(1) O(1) O(n)
minimum
usuwanie
analiza złożoności
heapsort
Dijkstra
wstawienie  wstawienie elementu
zastosowanie Kopca
zmiana priorytetu
bez zmiany
usunięcie  usunięcie elementu na podanej pozycji (a
priorytetu
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
wstawienie usunięcie minimum
Tablica
Własność kopca
tablica O(1) O(1) O(n)
dodawanie
minimum
posortowana tablica
usuwanie
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
wstawienie  wstawienie elementu
zmiana priorytetu
bez zmiany
priorytetu usunięcie  usunięcie elementu na podanej pozycji (a
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
wstawienie usunięcie minimum
Tablica
Własność kopca
tablica O(1) O(1) O(n)
dodawanie
minimum
posortowana tablica O(n)
usuwanie
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
wstawienie  wstawienie elementu
zmiana priorytetu
bez zmiany
priorytetu usunięcie  usunięcie elementu na podanej pozycji (a
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
wstawienie usunięcie minimum
Tablica
Własność kopca
tablica O(1) O(1) O(n)
dodawanie
minimum
posortowana tablica O(n) O(n)
usuwanie
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
wstawienie  wstawienie elementu
zmiana priorytetu
bez zmiany
priorytetu usunięcie  usunięcie elementu na podanej pozycji (a
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
wstawienie usunięcie minimum
Tablica
Własność kopca
tablica O(1) O(1) O(n)
dodawanie
minimum
posortowana tablica O(n) O(n) O(1)
usuwanie
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
wstawienie  wstawienie elementu
zmiana priorytetu
bez zmiany
priorytetu usunięcie  usunięcie elementu na podanej pozycji (a
nie o danej wartości)
minimum  znalezienie minimum
Wstęp
Kopiec,
wykorzystanie
do Dijkstry
Porównanie złożoności
Kopiec
Wstęp
wstawienie usunięcie minimum
Tablica
Własność kopca
tablica O(1) O(1) O(n)
dodawanie
minimum
posortowana tablica O(n) O(n) O(1)
usuwanie
analiza złożoności
kopiec O(log n) O(log n) O(log n)
heapsort
Dijkstra
zastosowanie Kopca
wstawienie  wstawienie elementu
zmiana priorytetu
bez zmiany
priorytetu usunięcie  usunięcie elementu na podanej pozycji (a
nie o danej wartości)
minimum  znalezienie minimum
Pełne drzewo binarne
Kopiec,
wykorzystanie
Pełne drzewo binarne
do Dijkstry
1
Kopiec
2 3
Wstęp
Tablica
Własność kopca
4 5 6 7
dodawanie
minimum
usuwanie 8 9 10 11 12
analiza złożoności
heapsort
Dijkstra
wyjaśnienie nazwy:
zastosowanie Kopca
zmiana priorytetu
binarne  każdy wierzchołek ma co najwyżej 2 synów
bez zmiany
priorytetu
pełne  liście znajdują się tylko na 2 poziomach przy
czym te na niższym poziomie są  z jednej strony
wierzchołki numerujemy jak na rysunku
w wierzchołkach będziemy trzymali liczby
heap[i] wartość w i-tym wierzchołku
Pełne drzewo binarne
Kopiec,
wykorzystanie
Pełne drzewo binarne
do Dijkstry
1
Kopiec
2 3
Wstęp
Tablica
Własność kopca
4 5 6 7
dodawanie
minimum
usuwanie 8 9 10 11 12
analiza złożoności
heapsort
Dijkstra
wyjaśnienie nazwy:
zastosowanie Kopca
zmiana priorytetu
binarne  każdy wierzchołek ma co najwyżej 2 synów
bez zmiany
priorytetu
pełne  liście znajdują się tylko na 2 poziomach przy
czym te na niższym poziomie są  z jednej strony
wierzchołki numerujemy jak na rysunku
w wierzchołkach będziemy trzymali liczby
heap[i] wartość w i-tym wierzchołku
Pełne drzewo binarne
Kopiec,
wykorzystanie
Pełne drzewo binarne
do Dijkstry
1
Kopiec
2 3
Wstęp
Tablica
Własność kopca
4 5 6 7
dodawanie
minimum
usuwanie 8 9 10 11 12
analiza złożoności
heapsort
Dijkstra
wyjaśnienie nazwy:
zastosowanie Kopca
zmiana priorytetu
binarne  każdy wierzchołek ma co najwyżej 2 synów
bez zmiany
priorytetu
pełne  liście znajdują się tylko na 2 poziomach przy
czym te na niższym poziomie są  z jednej strony
wierzchołki numerujemy jak na rysunku
w wierzchołkach będziemy trzymali liczby
heap[i] wartość w i-tym wierzchołku
Pełne drzewo binarne
Kopiec,
wykorzystanie
Pełne drzewo binarne
do Dijkstry
1
Kopiec
2 3
Wstęp
Tablica
Własność kopca
4 5 6 7
dodawanie
minimum
usuwanie 8 9 10 11 12
analiza złożoności
heapsort
Dijkstra
wyjaśnienie nazwy:
zastosowanie Kopca
zmiana priorytetu
binarne  każdy wierzchołek ma co najwyżej 2 synów
bez zmiany
priorytetu
pełne  liście znajdują się tylko na 2 poziomach przy
czym te na niższym poziomie są  z jednej strony
wierzchołki numerujemy jak na rysunku
w wierzchołkach będziemy trzymali liczby
heap[i] wartość w i-tym wierzchołku
Pełne drzewo binarne
Kopiec,
wykorzystanie
Pełne drzewo binarne
do Dijkstry
1
Kopiec
2 3
Wstęp
Tablica
Własność kopca
4 5 6 7
dodawanie
minimum
usuwanie 8 9 10 11 12
analiza złożoności
heapsort
Dijkstra
wyjaśnienie nazwy:
zastosowanie Kopca
zmiana priorytetu
binarne  każdy wierzchołek ma co najwyżej 2 synów
bez zmiany
priorytetu
pełne  liście znajdują się tylko na 2 poziomach przy
czym te na niższym poziomie są  z jednej strony
wierzchołki numerujemy jak na rysunku
w wierzchołkach będziemy trzymali liczby
heap[i] wartość w i-tym wierzchołku
Pełne drzewo binarne
Kopiec,
wykorzystanie
do Dijkstry
Pełne drzewo binarne
Kopiec 1
Wstęp
Tablica
2 3
Własność kopca
dodawanie
minimum
4 5 6 7
usuwanie
analiza złożoności
heapsort 8 9 10 11 12
Dijkstra
zastosowanie Kopca
zmiana priorytetu
bez zmiany Dlaczego taka numeracja jest wygodna?
priorytetu
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to x/2
Pełne drzewo binarne
Kopiec,
wykorzystanie
do Dijkstry
Pełne drzewo binarne
Kopiec 1
Wstęp
Tablica
2 3
Własność kopca
dodawanie
minimum
4 5 6 7
usuwanie
analiza złożoności
heapsort 8 9 10 11 12
Dijkstra
zastosowanie Kopca
zmiana priorytetu
bez zmiany Dlaczego taka numeracja jest wygodna?
priorytetu
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to x/2
Pełne drzewo binarne
Kopiec,
wykorzystanie
do Dijkstry
Pełne drzewo binarne
Kopiec 1
Wstęp
Tablica
2 3
Własność kopca
dodawanie
minimum
4 5 6 7
usuwanie
analiza złożoności
heapsort 8 9 10 11 12
Dijkstra
zastosowanie Kopca
zmiana priorytetu
bez zmiany Dlaczego taka numeracja jest wygodna?
priorytetu
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to x/2
Pełne drzewo binarne
Kopiec,
wykorzystanie
do Dijkstry
Pełne drzewo binarne
Kopiec 1
Wstęp
Tablica
2 3
Własność kopca
dodawanie
minimum
4 5 6 7
usuwanie
analiza złożoności
heapsort 8 9 10 11 12
Dijkstra
zastosowanie Kopca
zmiana priorytetu
bez zmiany Dlaczego taka numeracja jest wygodna?
priorytetu
lewy syn x to 2x
prawy syn x to 2x + 1
ojciec x to x/2
Kopiec
Kopiec,
wykorzystanie
do Dijkstry Kopiec
2
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie
3 6 7 6
minimum
usuwanie
8 4 9 8 7
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Własność kopca
zmiana priorytetu
bez zmiany
priorytetu
Kopcemnazywamy pełne drzewo binarne, które posiada
własność kopca, tzn. każdy wierzchołek ma przypisaną
wartość nie większą niż jego synowie.
Innymi słowy, dla wszystkich x zachodzi
heap[ x/2 ] heap[x].
Dodawanie elementu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
2
Kopiec
Wstęp
Tablica 3 5
Własność kopca
dodawanie
3 6 7 6
minimum
usuwanie
analiza złożoności
8 4 9 8 7
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
Jak dodać element do kopca?
bez zmiany
priorytetu
1
dodajemy element na koniec tablicy (własność kopca
może być zaburzona)
2
dopóki ojciec nowego elementu jest od niego większy,
to zamieniamy wartości w obu wierzchołkach
Dodawanie elementu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
2
Kopiec
Wstęp
Tablica 3 5
Własność kopca
dodawanie
3 6 7 6
minimum
usuwanie
analiza złożoności
8 4 9 8 7 4
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
Jak dodać element do kopca?
bez zmiany
priorytetu
1
dodajemy element na koniec tablicy (własność kopca
może być zaburzona)
2
dopóki ojciec nowego elementu jest od niego większy,
to zamieniamy wartości w obu wierzchołkach
Dodawanie elementu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
2
Kopiec
Wstęp
Tablica 3 5
Własność kopca
dodawanie
3 6 7 6
minimum
usuwanie
analiza złożoności
8 4 9 8 7 4
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
Jak dodać element do kopca?
bez zmiany
priorytetu
1
dodajemy element na koniec tablicy (własność kopca
może być zaburzona)
2
dopóki ojciec nowego elementu jest od niego większy,
to zamieniamy wartości w obu wierzchołkach
Dodawanie elementu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
2
Kopiec
Wstęp
Tablica 3 5
Własność kopca
dodawanie
3 6 4 6
minimum
usuwanie
analiza złożoności
8 4 9 8 7 7
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
Jak dodać element do kopca?
bez zmiany
priorytetu
1
dodajemy element na koniec tablicy (własność kopca
może być zaburzona)
2
dopóki ojciec nowego elementu jest od niego większy,
to zamieniamy wartości w obu wierzchołkach
Dodawanie elementu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
2
Kopiec
Wstęp
Tablica 3 5
Własność kopca
dodawanie
3 6 4 6
minimum
usuwanie
analiza złożoności
8 4 9 8 7 7
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
Jak dodać element do kopca?
bez zmiany
priorytetu
1
dodajemy element na koniec tablicy (własność kopca
może być zaburzona)
2
dopóki ojciec nowego elementu jest od niego większy,
to zamieniamy wartości w obu wierzchołkach
Dodawanie elementu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
2
Kopiec
Wstęp
Tablica 3 4
Własność kopca
dodawanie
3 6 5 6
minimum
usuwanie
analiza złożoności
8 4 9 8 7 7
heapsort
Dijkstra
zastosowanie Kopca
zmiana priorytetu
Jak dodać element do kopca?
bez zmiany
priorytetu
1
dodajemy element na koniec tablicy (własność kopca
może być zaburzona)
2
dopóki ojciec nowego elementu jest od niego większy,
to zamieniamy wartości w obu wierzchołkach
Jak dodać element do kopca?
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Własność kopca
HeapUp
dodawanie
minimum
Proces przenoszenia elementu kopca coraz wyżej w celu
usuwanie
analiza złożoności
przywrócenia własności kopca nazywamykopcowaniem w
heapsort
górę (HeapUp). W notatkach znajduje się implementacja
Dijkstra
zastosowanie Kopca
wstawiania elementu do kopca.
zmiana priorytetu
bez zmiany
priorytetu
Szukanie minimum
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Kopiec
Wstęp
2
Tablica
Własność kopca
3 5
dodawanie
minimum
usuwanie
3 6 7 6
analiza złożoności
heapsort
8 4 9 8 7
Dijkstra
zastosowanie Kopca
zmiana priorytetu
bez zmiany
priorytetu
Jak znalez
ć minimum w kopcu?
Minimum znajduje się oczywiście z korzeniu, czyli w
heap[1].
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
2
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie 3 6 7 6
minimum
usuwanie
8 4 9 8 7
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
7
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie 3 6 7 6
minimum
usuwanie
8 4 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
7
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie
3 6 7 6
minimum
usuwanie
8 4 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
3
Kopiec
Wstęp
7 5
Tablica
Własność kopca
dodawanie 3 6 7 6
minimum
usuwanie
8 4 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
3
Kopiec
Wstęp
7 5
Tablica
Własność kopca
dodawanie 3 6 7 6
minimum
usuwanie
8 4 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
3
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie 7 6 7 6
minimum
usuwanie
8 4 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
3
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie 7 6 7 6
minimum
usuwanie
8 4 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Usuwanie korzenia
Kopiec,
wykorzystanie
Kopiec
do Dijkstry
3
Kopiec
Wstęp
3 5
Tablica
Własność kopca
dodawanie 6 7 6
4
minimum
usuwanie
8 7 9 8
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Jak usunąć korzeń?
zmiana priorytetu
bez zmiany
priorytetu
1
w miejsce korzenia wstawiamy ostatni element
(własność kopca może być zaburzona)
2
dopóki wstawiony element jest większy od któregoś ze
swoich synów to zamieniamy go z synem o mniejszej
wartości
Jak usunąć korzeń?
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Własność kopca
HeapDown
dodawanie
minimum
Proces przenoszenia elementu kopca coraz niżej w celu
usuwanie
analiza złożoności
przywrócenia własności kopca nazywamykopcowaniem w
heapsort
dół (HeapDown). W notatkach znajduje się
Dijkstra
zastosowanie Kopca
implementacja usuwania korzenia z kopca.
zmiana priorytetu
bez zmiany
priorytetu
Usuwanie dowolnego elementu
Kopiec,
wykorzystanie
do Dijkstry
Problem
Kopiec
W jaki sposób możemy usunąć element na danej pozycji
Wstęp
Tablica
(niekoniecznie korzeń)?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Postąpimy podobnie jak w przypadku korzenia:
Dijkstra
zastosowanie Kopca
1
zmiana priorytetu w miejsce usuwanego elementu wstawiamy ostatni
bez zmiany
priorytetu
element
2
kopcujemy nowy element w górę
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Kopiec,
wykorzystanie
do Dijkstry
Problem
Kopiec
W jaki sposób możemy usunąć element na danej pozycji
Wstęp
Tablica
(niekoniecznie korzeń)?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Postąpimy podobnie jak w przypadku korzenia:
Dijkstra
zastosowanie Kopca
1
zmiana priorytetu w miejsce usuwanego elementu wstawiamy ostatni
bez zmiany
priorytetu
element
2
kopcujemy nowy element w górę
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Kopiec,
wykorzystanie
do Dijkstry
Problem
Kopiec
W jaki sposób możemy usunąć element na danej pozycji
Wstęp
Tablica
(niekoniecznie korzeń)?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Postąpimy podobnie jak w przypadku korzenia:
Dijkstra
zastosowanie Kopca
1
zmiana priorytetu w miejsce usuwanego elementu wstawiamy ostatni
bez zmiany
priorytetu
element
2
kopcujemy nowy element w górę
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Kopiec,
wykorzystanie
do Dijkstry
Problem
Kopiec
W jaki sposób możemy usunąć element na danej pozycji
Wstęp
Tablica
(niekoniecznie korzeń)?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Postąpimy podobnie jak w przypadku korzenia:
Dijkstra
zastosowanie Kopca
1
zmiana priorytetu w miejsce usuwanego elementu wstawiamy ostatni
bez zmiany
priorytetu
element
2
kopcujemy nowy element w górę
3
kopcujemy nowy element w dół
Usuwanie dowolnego elementu
Kopiec,
wykorzystanie
do Dijkstry
Problem
Kopiec
W jaki sposób możemy usunąć element na danej pozycji
Wstęp
Tablica
(niekoniecznie korzeń)?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Postąpimy podobnie jak w przypadku korzenia:
Dijkstra
zastosowanie Kopca
1
zmiana priorytetu w miejsce usuwanego elementu wstawiamy ostatni
bez zmiany
priorytetu
element
2
kopcujemy nowy element w górę
3
kopcujemy nowy element w dół
Analiza złożoności
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Własność kopca
dodawanie Analiza złożoności
minimum
usuwanie
Wszystkie opisane operacje działają w czasie
analiza złożoności
heapsort
proporcjonalnym do wysokości kopca, która jest
Dijkstra
logarytmiczna względem ilości elementów w kopcu.
zastosowanie Kopca
zmiana priorytetu
bez zmiany
priorytetu
Sortowanie przez kopcowanie (heapsort)
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Problem
Wstęp
Tablica
Jak można wykorzystać kopiec do uzyskania szybkiego 
Własność kopca
dodawanie
O(n log n) algorytmu sortowania?
minimum
usuwanie
analiza złożoności
heapsort
Rozwiązanie
Dijkstra
zastosowanie Kopca
Elementy tablicy, którą chcemy posortować wrzucamy do
zmiana priorytetu
bez zmiany
priorytetu kopca a następnie dopóki kopiec nie jest pusty, to
wypisujemy minimum i je usuwamy.
Sortowanie przez kopcowanie (heapsort)
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Problem
Wstęp
Tablica
Jak można wykorzystać kopiec do uzyskania szybkiego 
Własność kopca
dodawanie
O(n log n) algorytmu sortowania?
minimum
usuwanie
analiza złożoności
heapsort
Rozwiązanie
Dijkstra
zastosowanie Kopca
Elementy tablicy, którą chcemy posortować wrzucamy do
zmiana priorytetu
bez zmiany
priorytetu kopca a następnie dopóki kopiec nie jest pusty, to
wypisujemy minimum i je usuwamy.
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Własność kopca
Inne zastosowanie kopca
dodawanie
minimum
usuwanie
Jednym z najczęściej spotykanych zastosowań kopca jest
analiza złożoności
heapsort
użycie go do przyspieszenia algorytmu Dijkstry. Na
Dijkstra
początku przypomnimy ten algorytm.
zastosowanie Kopca
zmiana priorytetu
bez zmiany
priorytetu
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry
1
Kopiec oznacz wszystkie wierzchołki jako nieodwiedzone
Wstęp
Tablica 2
dla każdego v " V ustaw dis[v] = "
Własność kopca
dodawanie
3
ustaw dis[s] = 0
minimum
usuwanie
4
analiza złożoności dopóki istnieje nieodwiedzony wierzchołek o
heapsort
skończonej odległości:
Dijkstra
zastosowanie Kopca 1
niech v będzie wierzchołkiem nieodwiedzonym o
zmiana priorytetu
najmniejszej odległości
bez zmiany
priorytetu
2
oznacz v jako odwiedzony
3
zrelaksuj wszystkie krawędzie wychodzące z v
wąskie gardło: tą operację wykonujemy O(|V |) razy a
dotychczas zabierała ona czas O(|V |)
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Jak to przyspieszyć?
Kopiec
chcielibyśmy trzymać w kopcu wierzchołki
Wstęp
Tablica
nieodwiedzone i móc szybko wyciągać z niego
Własność kopca
dodawanie
wierzchołek x o najmniejszej wartości dis[x]
minimum
usuwanie
możemy trzymać w kopcu numery wierzchołków grafu
analiza złożoności
heapsort
przy kopcowaniu musimy wówczas porównywać
Dijkstra
zastosowanie Kopca
odpowiednie wartości w tablicy dis a nie bezpośrednio
zmiana priorytetu
bez zmiany
wartości trzymane w kopcu (dis[x] będziemy nazywać
priorytetu
priorytetem wartości x)
problem: priorytety mogą ulegać zmianie (ale tylko
maleć), co może zaburzyć własność kopca
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Jak to przyspieszyć?
Kopiec
chcielibyśmy trzymać w kopcu wierzchołki
Wstęp
Tablica
nieodwiedzone i móc szybko wyciągać z niego
Własność kopca
dodawanie
wierzchołek x o najmniejszej wartości dis[x]
minimum
usuwanie
możemy trzymać w kopcu numery wierzchołków grafu
analiza złożoności
heapsort
przy kopcowaniu musimy wówczas porównywać
Dijkstra
zastosowanie Kopca
odpowiednie wartości w tablicy dis a nie bezpośrednio
zmiana priorytetu
bez zmiany
wartości trzymane w kopcu (dis[x] będziemy nazywać
priorytetu
priorytetem wartości x)
problem: priorytety mogą ulegać zmianie (ale tylko
maleć), co może zaburzyć własność kopca
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Jak to przyspieszyć?
Kopiec
chcielibyśmy trzymać w kopcu wierzchołki
Wstęp
Tablica
nieodwiedzone i móc szybko wyciągać z niego
Własność kopca
dodawanie
wierzchołek x o najmniejszej wartości dis[x]
minimum
usuwanie
możemy trzymać w kopcu numery wierzchołków grafu
analiza złożoności
heapsort
przy kopcowaniu musimy wówczas porównywać
Dijkstra
zastosowanie Kopca
odpowiednie wartości w tablicy dis a nie bezpośrednio
zmiana priorytetu
bez zmiany
wartości trzymane w kopcu (dis[x] będziemy nazywać
priorytetu
priorytetem wartości x)
problem: priorytety mogą ulegać zmianie (ale tylko
maleć), co może zaburzyć własność kopca
Kopiec a algorytm Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Jak to przyspieszyć?
Kopiec
chcielibyśmy trzymać w kopcu wierzchołki
Wstęp
Tablica
nieodwiedzone i móc szybko wyciągać z niego
Własność kopca
dodawanie
wierzchołek x o najmniejszej wartości dis[x]
minimum
usuwanie
możemy trzymać w kopcu numery wierzchołków grafu
analiza złożoności
heapsort
przy kopcowaniu musimy wówczas porównywać
Dijkstra
zastosowanie Kopca
odpowiednie wartości w tablicy dis a nie bezpośrednio
zmiana priorytetu
bez zmiany
wartości trzymane w kopcu (dis[x] będziemy nazywać
priorytetu
priorytetem wartości x)
problem: priorytety mogą ulegać zmianie (ale tylko
maleć), co może zaburzyć własność kopca
Jak znalez
ć element w kopcu?
Kopiec,
wykorzystanie
do Dijkstry
Problem
Za każdym razem, gdy priorytet jakiegoś elementu się
Kopiec
zmniejszy musimy wykonać kopcowanie tego elementu w
Wstęp
Tablica
górę. Umiemy jednak wykonywać kopcowanie jedynie
Własność kopca
dodawanie
elementu na danej pozycji (a nie o danej wartości). Jak
minimum
usuwanie
rozwiązać ten problem?
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Rozwiązanie
zmiana priorytetu
bez zmiany
priorytetu Oprócz tablicy heap, będziemy trzymali tablicę where, gdzie
where[x] oznacza pozycję w kopcu wartości x, tzn.
heap[where[x]] = x. Przyjmujemy where[x] = 0, jeśli w
kopcu nie ma elementu x. Tablicę tę musimy uaktualniać za
każdym razem, gdy przemieszczamy elementy w kopcu.
Jak znalez
ć element w kopcu?
Kopiec,
wykorzystanie
do Dijkstry
Problem
Za każdym razem, gdy priorytet jakiegoś elementu się
Kopiec
zmniejszy musimy wykonać kopcowanie tego elementu w
Wstęp
Tablica
górę. Umiemy jednak wykonywać kopcowanie jedynie
Własność kopca
dodawanie
elementu na danej pozycji (a nie o danej wartości). Jak
minimum
usuwanie
rozwiązać ten problem?
analiza złożoności
heapsort
Dijkstra
zastosowanie Kopca
Rozwiązanie
zmiana priorytetu
bez zmiany
priorytetu Oprócz tablicy heap, będziemy trzymali tablicę where, gdzie
where[x] oznacza pozycję w kopcu wartości x, tzn.
heap[where[x]] = x. Przyjmujemy where[x] = 0, jeśli w
kopcu nie ma elementu x. Tablicę tę musimy uaktualniać za
każdym razem, gdy przemieszczamy elementy w kopcu.
Algorytm Dijkstry z kopcem
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Analiza złożoności
Własność kopca
dodawanie
nieodwiedzony wierzchołek o najmniejszej odległości
minimum
usuwanie
możemy znalez
ć teraz w czasie O(log |V |)
analiza złożoności
heapsort
relaksacja krawędzi zajmuje teraz czas O(log |V |), więc
Dijkstra
zastosowanie Kopca
relaksacja wszystkich krawędzi zajmuje czas
zmiana priorytetu
bez zmiany
O(|E| log |V |) i taka też jest złożoność całego algorytmu
priorytetu
Algorytm Dijkstry z kopcem
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Analiza złożoności
Własność kopca
dodawanie
nieodwiedzony wierzchołek o najmniejszej odległości
minimum
usuwanie
możemy znalez
ć teraz w czasie O(log |V |)
analiza złożoności
heapsort
relaksacja krawędzi zajmuje teraz czas O(log |V |), więc
Dijkstra
zastosowanie Kopca
relaksacja wszystkich krawędzi zajmuje czas
zmiana priorytetu
bez zmiany
O(|E| log |V |) i taka też jest złożoność całego algorytmu
priorytetu
Wady takiego rozwiązania
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Własność kopca Wady:
dodawanie
minimum
musimy zaimplementować kopiec z operacją zmiany
usuwanie
analiza złożoności
priorytetu, co może zająć dość dużo czasu
heapsort
Dijkstra gotowe implementacje kopca, o których dowiesz się na
zastosowanie Kopca
zmiana priorytetu jednych z następnych zajęć, nie posiadają tej operacji
bez zmiany
priorytetu
Wady takiego rozwiązania
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Wstęp
Tablica
Własność kopca Wady:
dodawanie
minimum
musimy zaimplementować kopiec z operacją zmiany
usuwanie
analiza złożoności
priorytetu, co może zająć dość dużo czasu
heapsort
Dijkstra gotowe implementacje kopca, o których dowiesz się na
zastosowanie Kopca
zmiana priorytetu jednych z następnych zajęć, nie posiadają tej operacji
bez zmiany
priorytetu
Inne rozwiązanie
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Inne rozwiązanie
Wstęp
Tablica
przedstawimy teraz rozwiązanie, które korzysta ze
Własność kopca
dodawanie
zwykłego kopca (bez operacji zmiany priorytetu)
minimum
usuwanie
analiza złożoności
do kopca będziemy wrzucać pary (dis[x], x)
heapsort
przyjmujemy porządek leksykograficzny na parach, tzn.
Dijkstra
zastosowanie Kopca
(x, y) < (a, b) wtw. x < a (" (x = a '" y < b)
zmiana priorytetu
bez zmiany
priorytetu
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległości
Inne rozwiązanie
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Inne rozwiązanie
Wstęp
Tablica
przedstawimy teraz rozwiązanie, które korzysta ze
Własność kopca
dodawanie
zwykłego kopca (bez operacji zmiany priorytetu)
minimum
usuwanie
analiza złożoności
do kopca będziemy wrzucać pary (dis[x], x)
heapsort
przyjmujemy porządek leksykograficzny na parach, tzn.
Dijkstra
zastosowanie Kopca
(x, y) < (a, b) wtw. x < a (" (x = a '" y < b)
zmiana priorytetu
bez zmiany
priorytetu
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległości
Inne rozwiązanie
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Inne rozwiązanie
Wstęp
Tablica
przedstawimy teraz rozwiązanie, które korzysta ze
Własność kopca
dodawanie
zwykłego kopca (bez operacji zmiany priorytetu)
minimum
usuwanie
analiza złożoności
do kopca będziemy wrzucać pary (dis[x], x)
heapsort
przyjmujemy porządek leksykograficzny na parach, tzn.
Dijkstra
zastosowanie Kopca
(x, y) < (a, b) wtw. x < a (" (x = a '" y < b)
zmiana priorytetu
bez zmiany
priorytetu
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległości
Inne rozwiązanie
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Inne rozwiązanie
Wstęp
Tablica
przedstawimy teraz rozwiązanie, które korzysta ze
Własność kopca
dodawanie
zwykłego kopca (bez operacji zmiany priorytetu)
minimum
usuwanie
analiza złożoności
do kopca będziemy wrzucać pary (dis[x], x)
heapsort
przyjmujemy porządek leksykograficzny na parach, tzn.
Dijkstra
zastosowanie Kopca
(x, y) < (a, b) wtw. x < a (" (x = a '" y < b)
zmiana priorytetu
bez zmiany
priorytetu
najmniejszy element w kopcu, odpowiada wówczas
wierzchołkowi o najmniejszej odległości
Problem zmiany priorytetu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Problem
Wstęp
Tablica
Co zrobić jeśli wartość dis[x] się zmieni?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Wrzucamy do kopca nową parę (dis[x], x). Przy takim
Dijkstra
zastosowanie Kopca
podejściu w kopcu będą znajdowały się śmieci 
zmiana priorytetu
bez zmiany
priorytetu nieaktualne pary postaci (d, x), gdzie d > dis[x]. Pary takie
po prostu pomijamy przy wyciąganiu ich z kopca.
Problem zmiany priorytetu
Kopiec,
wykorzystanie
do Dijkstry
Kopiec
Problem
Wstęp
Tablica
Co zrobić jeśli wartość dis[x] się zmieni?
Własność kopca
dodawanie
minimum
usuwanie
analiza złożoności Rozwiązanie
heapsort
Wrzucamy do kopca nową parę (dis[x], x). Przy takim
Dijkstra
zastosowanie Kopca
podejściu w kopcu będą znajdowały się śmieci 
zmiana priorytetu
bez zmiany
priorytetu nieaktualne pary postaci (d, x), gdzie d > dis[x]. Pary takie
po prostu pomijamy przy wyciąganiu ich z kopca.
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Nowa wersja algorytmu Dijkstry
Kopiec,
wykorzystanie
do Dijkstry
Algorytm Dijkstry z kopcem:
Kopiec
Wstęp
1
dla każdego v " V ustaw dis[v] = "
Tablica
Własność kopca
2
dodawanie ustaw dis[s] = 0
minimum
usuwanie
3
wrzuć do kopca parę (0, s)
analiza złożoności
heapsort
4
dopóki kopiec nie jest pusty
Dijkstra
1
zastosowanie Kopca wyciągnij najmniejszą parę z kopca, oznaczmy ją (d, v)
zmiana priorytetu
2
jeśli d > dis[v] to powróć do pkt. 4
bez zmiany
priorytetu
3
zrelaksuj wszystkie krawędzie wychodzące z v, jeśli
poprawia to odległość do wierzchołka x, to wrzuć parę
(dis[x], x) do kopca
Analiza algorytmu
Kopiec,
wykorzystanie
do Dijkstry
Analiza algorytmu
Kopiec
Wstęp
w tym przypadku rozmiar kopca wynosi O(|E|) a nie
Tablica
Własność kopca
O(|V |)
dodawanie
minimum
usuwanie
nie wpływa to jednak na złożoność, gdyż wynosi ona
analiza złożoności
heapsort
O(|E| log |E|) = O(|E| log |V |2) = O(2|E| log |V |) =
Dijkstra
O(|E| log |V |)
zastosowanie Kopca
zmiana priorytetu
jest on nieznacznie prostszy w implementacji niż
bez zmiany
priorytetu
poprzedni
nie wymaga kopca z operacją zmiany priorytetu
Analiza algorytmu
Kopiec,
wykorzystanie
do Dijkstry
Analiza algorytmu
Kopiec
Wstęp
w tym przypadku rozmiar kopca wynosi O(|E|) a nie
Tablica
Własność kopca
O(|V |)
dodawanie
minimum
usuwanie
nie wpływa to jednak na złożoność, gdyż wynosi ona
analiza złożoności
heapsort
O(|E| log |E|) = O(|E| log |V |2) = O(2|E| log |V |) =
Dijkstra
O(|E| log |V |)
zastosowanie Kopca
zmiana priorytetu
jest on nieznacznie prostszy w implementacji niż
bez zmiany
priorytetu
poprzedni
nie wymaga kopca z operacją zmiany priorytetu
Analiza algorytmu
Kopiec,
wykorzystanie
do Dijkstry
Analiza algorytmu
Kopiec
Wstęp
w tym przypadku rozmiar kopca wynosi O(|E|) a nie
Tablica
Własność kopca
O(|V |)
dodawanie
minimum
usuwanie
nie wpływa to jednak na złożoność, gdyż wynosi ona
analiza złożoności
heapsort
O(|E| log |E|) = O(|E| log |V |2) = O(2|E| log |V |) =
Dijkstra
O(|E| log |V |)
zastosowanie Kopca
zmiana priorytetu
jest on nieznacznie prostszy w implementacji niż
bez zmiany
priorytetu
poprzedni
nie wymaga kopca z operacją zmiany priorytetu
Analiza algorytmu
Kopiec,
wykorzystanie
do Dijkstry
Analiza algorytmu
Kopiec
Wstęp
w tym przypadku rozmiar kopca wynosi O(|E|) a nie
Tablica
Własność kopca
O(|V |)
dodawanie
minimum
usuwanie
nie wpływa to jednak na złożoność, gdyż wynosi ona
analiza złożoności
heapsort
O(|E| log |E|) = O(|E| log |V |2) = O(2|E| log |V |) =
Dijkstra
O(|E| log |V |)
zastosowanie Kopca
zmiana priorytetu
jest on nieznacznie prostszy w implementacji niż
bez zmiany
priorytetu
poprzedni
nie wymaga kopca z operacją zmiany priorytetu