Heapsort

10 Nov

Heapsort je třídící algoritmus prováděné za pomocídatové struktury halda (heap). Asymptotická časová složitost je vždy O(n log n). Heapsortje jedním z mála známých rychlých třídících algoritmů, které nepotřebují pomocnou paměť.
Halda je datová struktura podobná stromu a má podmínku že prvek xi je větší než x2i a x2i+1 (u jazyků s nulovým prvekm pole je větší než xi2+1 xi2+2). To znamená že na vrcholu (x1) je vždy nejvyšší prvek. Této vlastnosti se využívá při řazení, kde se nejprve vytvoří halda a poté se postupně odebírá vrchol.
Halda

Heapsort
Zde se nejprve vytvoří halda a poté se postupně vyberou nejvyšší prvky

A zde ještě heapsort v Pascalu:

type Pole = array[1..MAXN] of Integer;

procedure HeapSort(var A: Pole);
var i, x: integer;
procedure bublej(m, i: integer); { “zabublání” prvku }
{ m je velikost haldy, i je index zabublávaného prvku }
var j, x: integer;
begin
while 2*i<=m do begin
j:=2*i;
if (jA[j]) then j:=j+1;
if A[i]>=A[j] then break;
x:=A[i]; A[i]:=A[j]; A[j]:=x;
i:=j;
end;
end;
begin
for i:=N div 2 downto 1 do bublej(N,i); { bublej }
for i:=N downto 2 do begin { vybírej maximum }
x:=A[1]; A[1]:=A[i]; A[i]:=x;
bublej(i-1, 1);
end;
end;

One Response to “Heapsort”

  1. Family Vacation Ideas November 15, 2011 at 2:50 pm #

    I dont know what to say. This blog is fantastic. Thats not really a really huge statement, but its all I could come up with after reading this. You know so much about this subject. So much so that you made me want to learn more about it. Your blog is my stepping stone, my friend. Thanks for the heads up on this subject.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: