Heapsort

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.

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;