Sortowanie kopcowe
HeapSort
James Williams
Kopiec
Kopiec (heap) - struktura drzewa binarnego implementowanego w postaci tablicy.
Kopcem nazywamy częściowo uporządkowane drzewo binarne, spełniające warunki:
Wartości przechowywane należą do zbioru uporządkowanego,
Wartość przechowywana w każdym węz
le jest większa lub równa wartościom w
jego węzłach potomnych (własność kopca, heap property),
Wszystkie liście w drzewie leżą na co najwyżej dwóch sąsiadujących poziomach,
a liście na ostatnim poziomie szczelnie wypełniają jego lewą część. Elementy
zapełniają drzewo binarne poziomami od lewej do prawej (własność zupełności,
complete property),
Na ścieżkach od korzenia do liścia, elementy są posortowane nierosnąco.
ASD LJ S
Kopiec
Kopiec to zbiór węzłów ułożonych w zrównoważone drzewo binarne (wypełniane od
strony lewej do prawej) spełniające własność kopca i implemnetowane jako tablica.
1
15
2
12 3
6
4
11
5 6 7
10 2 3
8
1 9
8
1 2 3 4 5 6 7 8 9
A 15 12 6 11 10 2 3 1 8
ASD LJ S
Kopiec
Operacje na węzłach tablicowej implementacji kopca.
Ojciec (i) {
1
15
return (ðÅ‚i/2ûÅ‚)
ðÅ‚i/2ûÅ‚
2
12 3
}
6
i
Lsyn(i) { 4
11
5 6 7
10 2 3
return (2i)
2i+1
2i
}
8
1 9
8
Psyn(i) {
return (2i+1)
}
1 2 3 4 5 6 7 8 9
A 15 12 6 11 10 2 3 1 8
Dla każdego węzła i (z wyjątkiem korzenia) zachodzi (heap property) :
A[Ojciec(i)] e" A[i]
ASD LJ S
Kopiec
Zależność między wysokością h a liczbą węzłów w kopcu:
2h  1 < n d" 2h+1-1
2h d" n < 2h+1
h = ðÅ‚ lgn ûÅ‚
h=Åš(lgn)
Kopiec mający n węzłów i tworzony na podstawie pełnego drzewa binarnego jest
wysokoÅ›ci Åš(lgn) ( ðÅ‚ lgn ûÅ‚),
Podstawowe operacje na węzłach kopca działają w czasie co najwyżej
proporcjonalnym do wysokości drzewa, O(lgn).
ASD LJ S
Kopiec
Operacje wykonywane na kopcu:
1. INSERT  dopisywanie elementu na końcu kopca (1) a nastepnie jego poprawianie w górę
tak, aby zachować własności kopca.
2. Max  odczytanie wartości maksymalnej zapisanej w korzeniu drzewa.
3. DeleteMax  usunięcie korzenia(1), przeniesienie ostatniego elementu kopca do korzenia
(2) i poprawienie kopca w dół (3).
1
a) b)
Max
Max
2
3
UpHeap
DownHeap
2
1
Operacje kopca: a) dodawanie nowego elementu, b) usuwanie elementu maksymalnego.
ASD LJ S
Kopiec
Przywracanie własności kopca.
1
15
2
8 3
6
4
12
5 6 7
10 2 3
8
1 9
11
2
12
2
12
4
4
8
11
8
8 1 9
1 9 8
11
ASD LJ S
Kopiec
1
15
2
12 3
6
4
11
5 6 7
10 2 3
8
1 9
8
1 2 3 4 5 6 7 8 9
A
15 12 6 11 10 2 3 1 8
" n - liczba elementów tablicy,
" heapsize  liczba elementów kopca przechowywanych w tablicy, heapsize d" n,
" element tablicy A o indeksie większym niż heapsize nie jest elementem kopca.
ASD LJ S
Przywracanie kopca
Procedura przywracania kopca.
Heapify (A,i,heapsize)
{
synL=Lsyn(i);
synP=Psyn(i);
IF(synLd"heapsize and A[synL]>A[i])
wiekszy=synL;
ELSE
wiekszy=i;
IF(synPd"heapsize and A[synP]>A[wiekszy])
wiekszy=synP;
IF(wiekszy`"i){
(A[i]"!A[wiekszy]);
Heapify(A,wiekszy,heapsize);
}
TH(n) = O(lg n)
}
ASD LJ S
Budowanie kopca
Procedura budowania kopca.
1
2
CreateHeap(A,n)
2
8 3
{ 6
heapsize=n;
FOR i=ðÅ‚n/2ûÅ‚,...,1 {
4
12
5 6 7
10 15 3
Heapify(A,i,heapsize)
}
}
8
1 9
11
1 2 3 4 5 6 7 8 9
A
15 8 6 12 10 15 3 1 11
ASD LJ S
Budowanie kopca
1 1
2 2
2 2
8 3 8 3
6 15
4 4
12 12
5 6 7 5 6 7
10 15 3 10 6 3
8 8
1 9 1 9
11 11
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
A 2 8 15 12 10 6 3 1 11
A 2 8 6 12 10 15 3 1 11
ASD LJ S
Budowanie kopca
1
2
1
2
2
12 3
2 15
12 3
15
4
11
4
5 6 7
8 10 6 3
5 6 7
10 6 3
8
1 9
8
8
1 9
11
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
A 2 12 15 11 10 6 3 1 8
A 2 12 15 8 10 6 3 1 11
ASD LJ S
Budowanie kopca
1 1
15 15
2 2
12 3 12 3
2 6
4 4
11 11
5 6 7 5 6 7
10 6 3 10 2 3
8 8
1 9 1 9
8 8
1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9
A 15 12 6 11 10 2 3 1 8
A 15 12 2 11 10 6 3 1 8
ASD LJ S
Sortowanie kopcowe
Algorytm sortowania kopcowego.
HeapSort(A,n) Złożoność obliczeniowa algorytmu
HeapSort.
{
CreateHeap(A,n);
heapsize=n; T(n) = TCH(n) + (n-1) TH(n)
WHILE(heapsize>1){
TCH(n) = O(n) - złożoność CreateHeap
A[1]"!A[heapsize];
heapsize=heapsize 1;
TH(n) = O(lg n) - złożoność Heapify
Heapify(A,1,heapsize)
}
}
T(n) = O(n) + O(n) O(lg n) = O(nlgn).
ASD LJ S
Kolejka priorytetowa
Kolejka proiorytetowa (priority queue)  struktura danych, służąca do
przechowywania zbioru elementow, z których każdy ma przyporządkowaną wartość
klucza zw. priorytetem.
Implementacje kolejki priorytetowej:
Lista nieuporzÄ…dkowana,
Lista uporzÄ…dkowana,
Kopiec.
Interfejs kolejki proiorytetowej:
Znalezienie i usunięcie elementu o najwyższym priorytecie (ExtractMax),
Wstawianie elementu (Insert).
ASD LJ S
Interfejs kolejki priorytetowej
Procedura (ExtractMax).
Heap_ ExtractMax(A)
{
IF(heapsizee"1){
max=A[1];
A[1]=A[heapsize];
heapsize=heapsize 1;
Heapify(A,1,heapsize);
return(max);
}
}
Złożoność czasowa Heap_ExtractMax: O(lg n)
ASD LJ S
Interfejs kolejki priorytetowej
Procedura (Insert).
Heap_Insert(A,x)
{
heapsize=heapsize+1;
i=heapsize
WHILE(i>1 and Ojciec(i)A[i]=A[Ojciec(i)];
i=Ojciec(i);
}
A[i]=x
}
Złożoność czasowa Heap_Insert: O(lg n).
ASD LJ S
Zastosowanie kolejek priorytetowych
Systemy symulacyjne, w których priorytety odpowiadają chwilom wystąpienia
zdarzeń przeznaczonym do chronologicznego przetwarzania.
Planowanie zadań w systemach komputerowych, priorytety wskazują które
zadania mają być wykonane w pierwszej kolejności.
Obliczenia numeryczne, gdzie największy priortytet może oznaczać
pierszeństwo obsługi błędu.
ASD LJ S