Heapsort (Erlang)

From LiteratePrograms

Jump to: navigation, search
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
Retrieved from "http://literateprograms.org/Heapsort_%28Erlang%29"
Views
Personal tools