Heap Sort-sortowanie przez kopcowanie, Informatyka -all, INFORMATYKA-all


Temat: 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 reprezentujšca 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].

Początek formularza

Dół formularza



Wyszukiwarka

Podobne podstrony:
Sortowanie przez kopcowanie PHEAP
jak wykonac sortowanie przez zamiane wymiane wybor algorytm selection sort, PHP Skrypty
sortowania, ZiIP, 2 sem, Informatyka, Egzaminy
jak wykonac sortowanie przez wstawianie algorytm inserion sort, PHP Skrypty
Opisać popularne metody sortowania, edukacja i nauka, Informatyka
sortowanie przez zliczanie
Sortowanie przez scalanie PMERG
sortowanie przez wstawianie2
Sortowanie Przez Wstawianie
29 Sortowanie przez wybór (selekcję)
30 Sortowanie przez wstawianie Nieznany (2)
sortowanie przez wstawianie1
SORTOWANIE PRZEZ SCALANIE
heap sort
Algorytm sortowania przez wybór w porządku rosnącym
ALS - 009-005 - Program Sortowanie INSERTION SORT, Informatyka - uczelnia, WWSI i WAT, wwsi, SEM II,
Rozmowy przez Internet-IRC, Informatyka -all, INFORMATYKA-all
Wykorzystywanie komputera w zajęciach pozalekcyjnych przez u, wrzut na chomika listopad, Informatyka

więcej podobnych podstron