heapsort

procedure swap(var a: integer; var b: integer);
var
    tmp: integer;
begin
    tmp:=a;
    a:=b;
    b:=tmp;
end;

procedure shift_down(var a: array of integer; i: integer; len: integer);
var
    l: integer;
begin
    l:=i;
    if (2 * i + 1 < len) and (a[l] < a[2 * i + 1]) then
        l:=2 * i + 1;
    if (2 * i + 2 < len) and (a[l] < a[2 * i + 2]) then
        l:=2 * i + 2;
    swap(a[i], a[l]);
    if l <> i then
        shift_down(a, l, len);
end;

procedure shift_up(var a: array of integer; i: integer);
begin
    while (a[(i - 1) div 2] < a[i]) do
    begin
        swap(a[i], a[(i - 1) div 2]);
        i:=(i - 1) div 2;
    end;
end;

procedure heap_sort(var a: array of integer);
var
    i: integer;
begin
    for i:=0 to length(a) - 1 do
        shift_up(a, i);
    for i:=length(a) - 1 downto 1 do
    begin
        swap(a[0], a[i]);
        shift_down(a, 0, i);
    end;
end;

var
    a: array of integer;
    n, i: integer;

begin
    read(n);
    setlength(a, n);
    for i:=0 to n - 1 do
        read(a[i]);
    heap_sort(a);
    for i:=0 to n - 1 do
        write(a[i], ' ');
    writeln();
end.