Heapsort (Erlang)
This program is a code dump . Code dumps are - Heapsort (Erlang)
From LiteratePrograms
- Other implementations: C | Erlang
This program is a code dump.
Code dumps are articles with little or no documentation or rearrangement of code. Please help to turn it into a literate program. Also make sure that the source of this code does consent to release it under the MIT or public domain license.
<<heapsort.erl>>=
-module(heap).
-export([new/0, new/1, add/2, remove_root/1, sort/1]).
new() -> [].
new(L) -> add([], L).
add(Heap, []) -> Heap;
add(Heap, [H | T]) ->
add(up_heap(Heap, [ H ]), T).
up_heap(Heap, [H | T]) ->
PPos = trunc((length(Heap) + 1) / 2),
case PPos > 0 andalso lists:nth(PPos, Heap) > H of
true ->
{Upper, [P | Lower]} = lists:split(PPos - 1, Heap),
up_heap(Upper, [H | Lower ++ [P | T]]);
false ->
Heap ++ [H | T]
end.
remove_root([Root]) -> {Root, []};
remove_root([Root | Rest]) ->
{T, [H]} = lists:split(length(Rest) - 1, Rest),
{Root, down_heap([], [H | T])}.
down_heap(Heap, [H | T]) ->
CPos = length(Heap) + 1,
if
CPos > length(T) -> Heap ++ [H | T];
CPos =:= length(T) ->
C = lists:last(T),
if
H =< C -> Heap ++ [H | T];
true -> Heap ++ [C | lists:sublist(T, CPos - 1)] ++ [H]
end;
true ->
{Upper, [Left, Right | Lower]} = lists:split(CPos - 1, T),
if
(H =< Right) and (H =< Left) ->
Heap ++ [H | T];
Left =< Right ->
down_heap(Heap ++ [Left | Upper], [H, Right | Lower]);
true ->
down_heap(Heap ++ [Right | Upper], [Left, H | Lower])
end
end.
sort(L) -> sort(new(L), []).
sort([], Acc) -> lists:reverse(Acc);
sort(Heap, Acc) ->
{Root, Rest} = remove_root(Heap),
sort(Rest, [Root | Acc]).
| Download code |