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