heapsort

-module(heapsort).
-export([hsort/1]).
% Kodierung des Feldes: Nachfolger von Position i ist 2*i links und 2*i+1 rechts
% berechnet den Pfad zur ersten leeren Position
% l steht fuer links, r fuer rechts
% Beispiel: sort:calcPath(1). --> []
%       sort:calcPath(2). --> [l]
%       sort:calcPath(3). --> [r]
%       sort:calcPath(4). --> [l,l]
%       sort:calcPath(5). --> [l,r]
%       sort:calcPath(6). --> [r,l]
%       sort:calcPath(7). --> [r,r]
calcPath(Number) -> calcPath(Number,[]).
% aktuelle Position ist Wurzel
calcPath(1,Accu) -> Accu;
% aktuelle Position ist gerade
calcPath(Number,Accu) when Number rem 2 =:= 0 -> calcPath(Number div 2,[l|Accu]);
% aktuelle Position ist ungerade
calcPath(Number,Accu) when Number rem 2 =/= 0 -> calcPath((Number-1) div 2,[r|Accu]).

hsort(Liste) ->
    {Heap, N} = createHeap(Liste).
%   createList(Heap, N+1).

createHeap(Liste=[H|T]) ->
    Heap = {H, {}, {}},
    createHeap(Heap, T, 1).
createHeap(Heap, [], N) -> {Heap, N};
createHeap(Heap, Liste=[H|T], N) ->
    NewHeap = insertHeap(Heap, H,calcPath(N+1)),
    createHeap(NewHeap, T, N+1).
% 4 8 3 9 6
%insertHeap({}, E,[]) -> {E,{}, {}};
insertHeap(Heap={Zh, L, R}, E, Steps = [l|_]) when E > Zh ->
    {E, Lneu={Zh, {},{} }, {}};
insertHeap(Heap={Zh, L, R}, E, Steps = [r|_]) when E > Zh ->
    {E, L, {Rneu=Zh,{},{}}};

insertHeap(Heap={Zh, L, R}, E, Steps = [l|_]) when E =< Zh ->
    {Zh, Lneu={E, {},{} }, {}};
insertHeap(Heap={Zh, L, R}, E, Steps = [r|_]) when E =< Zh ->
    {Zh, L, {Rneu=E,{},{}}};

insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E > Zh ->
    {E, insertHeap(L,Zh, T), R};
insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E > Zh ->
    {E, L, insertHeap(R,Zh, T)};

insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E =< Zh ->
    {Zh, insertHeap(L,E, T), R};
insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E =< Zh ->
    {Zh, L, insertHeap(R,E, T)}.