Kopce.
Załóżmy, że A jest tablicą reprezentującą kopiec. Korzeniem
drzewa jest A[1], a mając dany indeks i węzła, można łatwo
obliczyć indeksy jego ojca parent(i), lewego syna left(i) i prawego
Kopiec (binarny) to tablicowa struktura danych, którą można
syna right(i):
traktować jako drzewo binarne, pełne na wszystkich poziomach z
wyjątkiem być może najniższego, który jest wypełniony od lewej parent(i) = i/2 , left(i) = 2i, right(i) = 2i + 1.
strony do pewnego miejsca.
Lemat 5.1
Na przykład tablicy [10, 9, 8, 5, 6, 4, 7, 2, 1, 3] odpowiada drzewo
Kopiec n-elementowy ma wysokość log n .
Dowód: Niech h będzie wysokością kopca. Ponieważ pełne drzewo
10
binarne o wysokości h zawiera 2h+1 - 1 elementów (Lemat 2.1),
9 8
więc 2h d" n < 2h+1, stąd h d" log n < h + 1, czyli h = log n .
5 6 4 7
Lemat 5.2
Liście n-elementowego kopca to węzły o indeksach
2 1 3
n/2 + 1, n/2 + 2, . . . , n.
Dowód: Liść to węzeł, który nie ma synów. Zatem i jest indeksem
liścia wtedy i tylko wtedy, gdy left(i) > n, czyli i > n/2.
Przywracanie własności kopca.
Kopce występują w dwóch odmianach: typu max i typu min.
MAX-HEAPIFY jest procedurą służącą do przywracania własności
Własność kopca typu max:
kopca typu max.
dla każdego węzła i, który nie jest korzeniem, zachodzi
A[parent(i)] e" A[i].
Jej danymi wejściowymi są: tablica A, rozmiar kopca n oraz indeks
Największy element kopce typu max jest umieszczony w korzeniu, i d" n.
a poddrzewa każdego węzła zawierają wartości nie większe niż
Zakładamy, że lewe i prawe poddrzewa węzła o indeksie i są
wartość w tym węz
le.
kopcami typu max, ale element A[i] może być mniejszy od któregoś
Własność kopca typu min:
ze swoich synów, przez co narusza własność kopca typu max.
dla każdego węzła i, który nie jest korzeniem, zachodzi
A[parent(i)] d" A[i].
W wyniku działania MAX-HEAPIFY, element A[i]  spływa w dół
drzewa tak, że poddrzewo o korzeniu w węz
le i staje siÄ™ kopcem
Najmniejszy element kopca typu min znajduje siÄ™ w korzeniu.
typu max.
Procedura MAX-HEAPIFY Działanie MAX-HEAPIFY
MAX-HEAPIFY(A, n, i)
W każdym kroku jest wybierany największy z elementów A[i],
1. begin
A[left(i)], A[right(i)], a jego indeks jest zachowywany w zmiennej
2. l := left(i);
largest.
3. r := right(i);
Jeśli największy jest A[i], to poddrzewo o korzeniu w i jest kopcem
4. if l d" n and A[l] > A[i]
typu max i procedura siÄ™ zatrzymuje.
5. then largest := l
6. else largest := i;
W przeciwnym wypadku jeden z synów jest największym
7. if r d" n and A[r] > A[largest]
elementem i następuje zamiana A[i] z A[lergest], co powoduje że
8. then largest := r;
węzeł i i jego synowie spełniają własność kopca typu max.
9. if largest = i then

Węzeł largest ma jednak teraz wartość A[i] i dlatego poddrzewo o
10. begin
korzeniu largest może nie spełniać własności kopca typu max.
11. zamień A[i] z A[largest];
12. MAX-HEAPIFY(A, n, largest);
Żeby to naprawić wywołujemy MAX-HEAPIFY rekurencyjnie na
13. end;
tym poddrzewie.
14. end;
Przykład: działanie procedury MAX-HEAPIFY(A, 10, 2)
Czas działania MAX-HEAPIFY
i l r largest A
2 4 5 4 [10, 3, 8, 9, 6, 4, 7, 2, 5, 1]
Oznaczmy:
4 8 9 9 [10, 9, 8, 3, 6, 4, 7, 2, 5, 1]
c - Å‚Ä…czny czas wykonania instrukcji w wierszach 2 11,
9 18 19 9 [10, 9, 8, 3, 6, 4, 7, 2, 3, 1]
10 10
T (h) - pesymistyczny czas działania procedury MAX-HEAPIFY na
drzewie o wysokości h.
3 8 9 8
Poddrzewo, na którym wywołujemy MAX-HEAPIFY rekurencyjnie
9 6 4 7 3 6 4 7
w wierszu 12 ma wysokość d" h - 1, stąd
2 5 1 2 5 1
T (h) d" c + T (h - 1).
A
atwo wykazać przez indukcję, że T (h) d" c(h + 1), czyli
10
T (h) = O(h).
9 8
Stąd i z Lematu 5.1 otrzymujemy, że MAX-HEAPIFY działa na
5 6 4 7
drzewie rozmiaru k w pesymistycznym czasie O(log k).
2 3 1
Działanie BUILD-MAX-HEAP dla A = [1, 4, 7, 3, 10, 6, 2, 8, 9, 5].
Budowanie kopca.
Na kolejnych rysunkach pokazano drzewo przed wywołaniem
MAX-HEAPIFY w wierszu 3. Element o indeksie i zaznaczono na
Procedury MAX-HEAPIFY możemy użyć do przekształcenia
czerwono.
dowolnej tablicy A[1..n] w kopiec typu max.
1 1
Na mocy Lematu 5.2 wszystkie elementy podtablicy
A[( n/2 + 1)..n] są liśćmi, zatem każdy z nich jest już
4 7 4 7
1-elementowym kopcem.
3 10 6 2 3 10 6 2
Procedura BUILD-MAX-HEAP przechodzi przez pozostałe węzły i
8 9 5 8 9 5
wywołuje w każdym z nich MAX-HEAPIFY.
BUILD-MAX-HEAP(A)
1 1
1. begin
2. for i := n/2 downto 1 do
4 7 4 7
3. MAX-HEAPIFY(A, n, i);
9 10 6 2 9 10 6 2
4. end;
8 3 5 8 3 5
Inicjowanie: Podczas pierwszego sprawdzania jest i = n/2 .
Każdy z węzłów o indeksach n/2 + 1, . . . , n jest liściem na mocy
1 10
Lematu 5.2, jest więc korzeniem trywialnego kopca typu max.
10 7 9 7
Utrzymanie: Zauważmy, że synowie węzła i mają indeksy większe
niż i, więc na mocy niezmiennika są korzeniami kopców typu max.
9 5 6 2 8 5 6 2
Zatem po wywołaniu MAX-HEAPIFY(A, n, i), węzeł i będzie
8 3 4 1 3 4 kopcem typu max, a węzły i + 1, . . . , n nadal będą korzeniami
kopców typu max. Niezmiennik pętli będzie wiec spełniony
Aby pokazać, że procedura BUILD-MAX-HEAP działa poprawnie,
podczas następnego sprawdzania warunku pętli.
wykażemy następujący niezmiennik pętli:
Zakończenie: Podczas ostatniego sprawdzania i = 0. Na mocy
Podczas każdego sprawdzania warunku pętli for, każdy z węzłów o
niezmiennika, każdy z węzłów 1, . . . , n jest korzeniem kopca typu
indeksach i + 1, i + 2, . . . , n jest korzeniem węzła typu max.
max. W szczególności jest nim węzeł o indeksie 1, czyli całe
drzewo jest kopcem typu max.
Czas działania BUILD-MAX-HEAP.
Ustalmy dowolny węzeł x kopca rozmiaru n i niech d oznacza jego
głębokość, a h wysokość, to znaczy wysokość poddrzewa o Zauważmy, że szereg
"

korzeniu x. Wtedy d + h jest wysokością całego kopca, czyli h
d + h = log n .
2h
h=1
Dowolne drzewo binarne ma co najwyżej 2d węzłów o głębokości
jest zbieżny (np. na mocy kryterium Cauchy ego). Oznaczając
d, a zatem n-elementowy kopiec ma co najwyżej
przez s jego sumę otrzymujemy, że dla dowolnego n zachodzi
2 log n -h d" n/2h log n

h
< s,
2h
węzłów o głębokości h.
h=1
Czas działania procedury MAX-HEAPIFY wywołanej w węz
le o
czyli T (n) = O(n).
wysokości h wynosi O(h), zatem pesymistyczny czas działania
Zatem pesymistyczny czas działania procedury BUILD-MAX-HEAP
BUILD-MAX-HEAP dla tablicy n-elementowej szacuje siÄ™ przez
dla tablicy n-elementowej wynosi O(n).
ëÅ‚ öÅ‚
log n log n

n h
íÅ‚ Å‚Å‚
T (n) d" O(h) = O n .
2h 2h
h=1 h=1
Sortowanie przez kopcowanie (heapsort). Procedura HEAPSORT
Algorytm heapsort sortuje tablicę A[1..n] w następujący sposób.
Najpierw tablica jest przekształcana w kopiec typu max, za HEAPSORT(A)
pomocÄ… BUILD-MAX-HEAP. 1. begin
2. BUILD-MAX-HEAP(A);
Wtedy A[1] jest największym elementem, więc umieszczamy
3. for i := n downto 2 do
go na swoim miejscu, zamieniajÄ…c z A[n].
4. begin
Jeżeli teraz  wyrzucimy ostatni węzeł z kopca, to otrzymaną
5. zamień A[1] z A[i];
tablicę A[1..n - 1] łatwo przekształcić w kopiec typu max.
6. MAX-HEAPIFY(A, i - 1, 1);
Ponieważ synowie korzenia są wierzchołkami kopca typu max,
7. end;
wiec wystarczy wywołać MAX-HEAPIFY(A, n - 1, 1).
8. end;
Ten proces jest powtarzany dla coraz mniejszych kopców, aż
do uzyskania kopca rozmiaru 2.
Poprawność HEAPSORT
Utrzymanie:
Załóżmy, że niezmiennik jest spełniony na początku iteracji.
Aby pokazać, że HEAPSORT poprawnie sortuje tablicę, wykażemy
następujący niezmiennik pętli:
Ponieważ A[1..i] jest kopcem typu max zawierającym i
najmniejszych elementów z tablicy wejściowej, więc A[1] jest
Podczas każdego sprawdzania warunku pętli for podtablica A[1..i]
największym z i najmniejszych elementów.
jest kopcem typu max zawierającym i najmniejszych elementów z
tablicy wejściowej, a A[i + 1..n] zawiera posortowanych n - i
Zamiana A[1] z A[i] w wierszu 5 powoduje, że A[i..n] zawiera
największych elementów z tablicy wejściowej.
posortowanych n - (i - 1) największych elementów z tablicy
wejściowej.
Inicjowanie:
Wywołanie MAX-HEAPIFY(A, i - 1, 1) w wierszu 6 powoduje
Podczas pierwszego sprawdzania jest i = n. Tablica A[1..n] jest
odtworzenie własności kopca typu max w podtablicy A[1..i - 1],
kopcem typu max zbudowanym z elementów tablicy wejściowej za
która teraz zawiera i - 1 najmniejszych elementów tablicy
pomocÄ… procedury BUILD-MAX-HEAP(A) w wierszu 2.
wejściowej.
Podtablica A[i + 1..n] jest pusta.
Przykład.
Działanie HEAPSORT dla A = [1, 4, 7, 3, 10, 6, 2, 8, 9, 5]. Każdy
Zakończenie:
rysunek przedstawia kopiec typu max na poczÄ…tku kolejnej iteracji
Na końcu mamy i = 1.
pętli for. Posortowaną część tablicy nie należącą do kopca
zaznaczono na czerwono.
Na mocy niezmiennika, A[1] jest najmniejszym elementem tablicy
wejściowej, a A[2..n] zawiera posortowanych n - 1 największych
10 9
elementów z tablicy wejściowej.
9 7 8 7
Zatem cała tablica A[1..n] jest posortowaną tablicą wejściową
8 5 6 2 4 5 6 2
1 3 4 1 3 10
4 3
8 7
3 2 1 2
5 7 5 6
1 5 6 7 4 5 6 7
4 3 6 2 4 3 1 2
8 9 10 8 9 10
1 9 10 8 9 10
2 1
6 5
1 3 2 3
5 2 4 2
4 5 6 7 4 5 6 7
4 3 1 7 1 3 6 7
8 9 10 8 9 10
8 9 10 8 9 10
Ostatni rysunek przedstawia posortowanÄ… tablicÄ™
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
Czas działania algorytmu heapsort.
Pesymistyczny czas działania algorytmu heapsort na tablicy
n-elementowej wynosi O(n log n), ponieważ budowa kopca przez
BUILD-MAX-HEAP zajmuje czas O(n), a każde z n - 1 wywołań
MAX-HEAPIFY zajmuje czas O(log n).
T (n) = O(n) + (n - 1)O(log n),
T (n) = O(n log n).
Otrzymaliśmy takie samo oszacowanie O(n log n) jak dla
sortowania przez scalanie. Jednak w odróżnieniu od sortowania
przez scalanie, heapsort działa w miejscu: tylko stała liczba
elementów jest w czasie działania algorytmu przechowywana poza
tablicą wejściową.