Heapfinal_sami

-module(heapsortCarl).
-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).


createList({}, _N)
->[];
createList(Heap={Z, _L, _R}, N)
-> HeapNeu = removeMin(Heap, calcPath(N-1)), createList(HeapNeu, N-1)++[Z].


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)}.

peekLast(_Heap={Z, L, R}, [r | []])
-> {E, _, _ } = R,
   {{Z, L, {}}, E};
peekLast(_Heap={Z, L, _R}, [l | []])
-> {E, _, _ } = L,
   {{Z, {}, {}}, E};
peekLast(_Heap={Z, L, R}, [l | Schritte])
-> {Lneu, E} = peekLast(L, Schritte),
   {{Z, Lneu, R}, E};
peekLast(_Heap={Z, L, R}, [r | Schritte])
-> {Rneu, E} = peekLast(R, Schritte),
   {{Z, L, Rneu}, E}.

removeMin(_Heap={_Z, {}, {}}, [])
-> {};
removeMin(Heap={_Z, _L ,_R}, Schritte)
-> {{_Zneu, Lneu, Rneu}, E} = peekLast(Heap, Schritte),
   toHeap ({E, Lneu, Rneu}).

toHeap(_Heap={Z, _L={LZ, _, _}, {} }) when LZ>Z
-> {LZ, {Z, {}, {}}, {}};

toHeap(_Heap={Z, L={LZ, _LL, _LR}, _R={RZ, RL, RR}}) when RZ>LZ, RZ>Z
-> {RZ, L, toHeap({Z, RL, RR})};

toHeap(_Heap={Z, _L={LZ, LL, LR}, R={RZ, _RL, _RR}}) when LZ>RZ, LZ>Z %links ist am grossten
-> {LZ, toHeap({Z, LL, LR}), R};

toHeap(Heap) %%ende, Z ist am grossten
-> Heap.