HeapSort - sortowanie przez kopcowanie

HeapSort - sortowanie przez kopcowanie

Kopiec (binarny) jest to tablicowa struktura danych, która mozna rozpatrywac jako pelne drzewo binarne.
Kazdy wezel drzewa odpowiada elementowi tablicy, w którym podana jest wartoc wezla.
Drzewo jest pelne na wszystkich poziomach z wyjatkiem byc moze najnizszego, który jest wypelniony od strony lewej do pewnego miejsca.
Tablica A reprezentujca kopiec ma dwa atrybuty:
· length, oznaczajacy liczbe wszystkich elementów tablicy
· heapsize, okreslajacy liczbe elementów kopca przechowywanych w tablicy
heapsize <= length
Korzeniem kopca jest A[0]
Majac dany indeks i-wezla mozna obliczyc lewego syna left(i) i prawego syna right(i)
left(i)
return i*2+1;
right(i)
return i*2+2;
Wartoc przechowywana w i-wezle zawsze jest wieksza badz równa warotosci przechowywanej w wezle potomnym.
A[i] >= A[left(i)] && A[i] >= A[right(i)]


Przykład kopca :


16
/ \\\\
14 10
/ \\\\ / \\\\
8 7 9 3
/ \\\\ /
2 4 1


reprezentacja tego samego kopca w postaci tablicy:

0 1 2 3 4 5 6 7 8 9
-----------------------------------------------------
16 14 10 8 7 9 3 2 4 1
------------------------------------------------------


Cala tablica traktowana jest jako kopiec, zatem:
heapsize = 10;
length = 10;
obliczenie lewego i prawego syna wezla nr 3 (przechowywana jest tam wartosc 8)
left(3) = 3*2+1 = 7 , na pozycji nr 7 w tablicy A jest liczba 2
rightt(3) = 3*2+2 = 8 , na pozycji nr 8 w tablicy A jest liczba 4


Procedury potrzebne do realizacji sortowania:


Kopcuj
Zadaniem procedury kopcuj jest spowodowanie, zeby wartosc A[i] \\\"splynela\\\" w dól kopca tak, zeby poddrzewo zaczepione w wezle i stalo sie kopcem.
kopcuj(A, i){
l=left(i)
r=right(i)
if l<= heapsize && A[l]>A[i]
then largest=l
else largest=i
if r <= heapsize && A[r]>A[largest]
then largest=r
if larfest != i
then {
zamien A[i] <-> A[largest]
kopcuj (A, largest)
}
}

BudujKopiec
Procedura ta buduje kopiec w sposób wstepujacy. Ze wzgledu na to, ze najnizsze liscie sa drzewami jednoelementowymi, to sa one jednoczesnie kopcami jednoelementowymi które nie maja poddrzew. Zaczyna wiec do wezla który posiada poddrzewo. Wezel ten ma indeks równy length/2-1
budujKopiec(A)
{
heapSize=length
for i=length/2-1 downto 0
kopcuj(A,i)
}

HeapSort

heapSort(A)
{
budujKopiec(A)
for i=length-1 downto 1
{
zamien A[0]<->A[i]
heapSize = heapSize - 1
kopcuj(A,0)
}
}
przyklad:
Dzialanie procedury heapSort dla drzewa zawierajacego 6 elementów
a) struktura kopca zaraz po jego zbudowaniu budujKopiec(A)
b-f) kolejne fazy sortowania po kazdym wywolaniu kopcuj
Liczby podkreslone zostaly usuniete z kopca poprzez zmniejszenie heapsize po zamien A[0]<->A[i].