heap sort

	Aktualizacja: 2005-02-12
sortowanie stogowe, sortowanie przez kopcowanie
Algorytm zaliczany do "ciekawszych" metod sortowania. jest on szybki oraz nie pochłania wiele zasobów pamięci. Jego złożoność obliczeniowa to O(n * ln(n)).

W tej metodzie sortowania jest wykorzystywana struktura danych zwana kopcem. Elementy tablicy tworzą kopiec, jeżeli dla każdego indeksu i zachodzi warunek:

A[i/2] >= A[i]

Tablicę można przedstawić jako drzewo binarne, w którym kolejne jej elementy są umieszczone poziomami od góry. Dla tablicy o siedmiu elementach drzewo binarne ma następującą postać:

Drzewo binarne jest kopcem, jeśli każdy element jest większy lub równy niż elementy w drzewie leżące pod nim na poziomach niższych.

Z warunku kopca (w obu sformułowaniach) wynika m.in., że w korzeniu takiego drzewa (czyli na początku tablicy) znajduje się element maksymalny.

Bardzo ważną procedurą w algorytmie, który chcemy opisać, jest przywracanie własności kopca dla pewnego elementu A[i]. Przy wywołaniu tej procedury zakłada się, że drzewa zaczepione w lewym i prawym synu wierzchołka zawierającego element A[i] są kopcami. Po zakończeniu działania procedury, drzewo zaczepione w wierzchołku zawierającym A[i] będzie spełniać własność kopca. Działanie tej procedury jest następujące:

• Jeśli element jest mniejszy od jednego ze swych synów, to zamień go z tym synem, który ma większą wartość.

• Wywołaj procedurę rekurencyjnie dla tego z synów, który zmienił wartość.

Mając tablicę, która ma własność kopca, oraz procedurę przywracania własności kopca dla zaburzonego elementu tablicy można podać następujący algorytm porządkowania:

• Dana jest tablica A[1..n] będąca kopcem, wobec tego element A[1] jest maksymalny.

• Niech m oznacza ostatni element kopca; na początku kopiec obejmuje całą tablicę, więc m jest równe n.

• Zamień ze sobą elementy A[1] i A[m].

• Zmniejsz m o 1.

• Przywróć własność kopca dla tablicy A[1..m] zaczynając od elementu A[1].

• Wróć do kroku 3.

Pozostaje jeszcze wyjaśnić, w jaki sposób zbudować kopiec w kroku 1. Wykorzystywana jest do tego opisana wyżej procedura przywracania własności kopca, działająca na elementach tablicy w pewnej kolejności. Elementy tablicy, które są liśćmi drzewa można traktować jak jednoelementowe kopce. Procedura budująca kopiec wywołuje procedurę przywracającą własność kopca dla każdego wierzchołka, który nie jest liściem, zaczynając od elementu leżącego najbliżej końca tablicy, a kończąc na korzeniu drzewa.

http://www.zs37.waw.pl/Sortowanie/HeapExSort.html

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].

http://neo.dmcs.p.lodz.pl/aisd/zaawansowane_algorytmy_sortowania.pdf

http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/index.html

// Konstruowanie kopca

//-------------------------------------------------

// (C)2005 mgr Jerzy Wałaszek

// I Liceum Ogólnokształcące

// im. K. Brodzińskiego

// w Tarnowie

//-------------------------------------------------

#include <iostream>

using namespace std;

main()

{

const int N = 31; // liczba elementów

int d[N + 1],i,j,k,x;

srand((unsigned)time(NULL));

cout << " Tworzenie kopca\n"

"----------------------\n"

"(C)2005 Jerzy Walaszek\n\n";

// Inicjujemy zbiór d[] liczbami pseudolosowymi od 0 do 9

for(i = 1; i <= N; i++) d[i] = rand() % 10;

// Budujemy kopiec

for(i = 2; i <= N; i++)

{

j = i; k = j / 2;

x = d[i];

while((k > 0) && (d[k] < x))

{

d[j] = d[k];

j = k; k = j / 2;

}

d[j] = x;

}

// Prezentujemy wyniki

x = (N + 1) / 2; k = 2;

for(i = 1; i <= N; i++)

{

for(j = 1; j <= x - 1; j++) cout << " ";

cout << d[i];

for(j = 1; j <= x; j++) cout << " ";

if(i + 1 == k)

{

k += k; x /= 2; cout << endl;

}

}

// Gotowe

cout << endl << endl;

system("PAUSE");

}

Schemat blokowy

Algorytm tworzy kopiec w tym samym zbiorze wejściowym d[ ]. Nie wymaga zatem dodatkowych struktur danych i ma złożoność pamięciową klasy O(n).

Pętla nr 1 wyznacza kolejne elementy wstawiane do kopca. Pierwszy element pomijamy, ponieważ zostałby i tak na swoim miejscu. Dlatego pętla rozpoczyna wstawianie od elementu nr 2.

Wewnątrz pętli nr 1 inicjujemy kilka zmiennych:

j	- pozycja wstawianego elementu (liścia)
k	- pozycja elementu nadrzędnego (przodka)
x	- zapamiętuje wstawiany element

Następnie rozpoczynamy pętlę warunkową nr 2, której zadaniem jest znalezienie w kopcu miejsca do wstawienia zapamiętanego elementu w zmiennej x. Pętla ta wykonuje się do momentu osiągnięcia korzenia kopca (k = 0) lub znalezienia przodka większego od zapamiętanego elementu. Wewnątrz pętli przesuwamy przodka na miejsce potomka, aby zachować warunek kopca, a następnie przesuwamy pozycję j na pozycję zajmowaną wcześniej przez przodka. Pozycja k staje się pozycją nowego przodka i pętla się kontynuuje. Po jej zakończeniu w zmiennej j znajduje się numer pozycji w zbiorze d[ ], na której należy umieścić element w x.

Po zakończeniu pętli nr 1 w zbiorze zostaje utworzona struktura kopca.
 

http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/index.html

http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/index.html

---