[erlang-questions] How can I implement a priority queue with Erlang?

Jeffrey Chen <>
Thu Aug 30 14:33:31 CEST 2007


I'm trying to implement a priority queue using heap struct. But I
can't do that efficient. Can anybody help me? I'll post my code below.
Thanks.


CODE:
exchange([], _, _, _, _, _) ->
    [];
exchange([_ | Rest], IndexA, ValueA, IndexB, ValueB, Index) when
IndexA == Index ->
    [ValueB | exchange(Rest, IndexA, ValueA, IndexB, ValueB, Index + 1)];
exchange([_ | Rest], IndexA, ValueA, IndexB, ValueB, Index) when
IndexB == Index ->
    [ValueA | exchange(Rest, IndexA, ValueA, IndexB, ValueB, Index + 1)];
exchange([Head | Rest], IndexA, ValueA, IndexB, ValueB, Index) ->
    [Head | exchange(Rest, IndexA, ValueA, IndexB, ValueB, Index + 1)].


%%% Heap %%%

max_heapify(Heap, Index) when Index * 2 > length(Heap) ->
    Heap;
max_heapify(Heap, Index) ->
    IndexValue = lists:nth(Index, Heap),

    LeftIndex  = 2 * Index,
    LeftValue  = lists:nth(LeftIndex, Heap),

    if
        2 * Index + 1 > length(Heap) ->
            RightIndex = LeftIndex,
            RightValue = LeftValue;
        true ->
            RightIndex = 2 * Index + 1,
            RightValue = lists:nth(RightIndex, Heap)
    end,

    if
        LeftValue > IndexValue, LeftValue >= RightValue ->
            LargestIndex = LeftIndex,
            LargestValue = LeftValue;
        RightValue > IndexValue, RightValue >= LeftValue ->
            LargestIndex = RightIndex,
            LargestValue = RightValue;
        true ->
            LargestIndex = Index,
            LargestValue = IndexValue
    end,

    if
        LargestIndex /= Index ->
            NewHeap = exchange(Heap, Index, IndexValue, LargestIndex,
LargestValue, 1),
            max_heapify(NewHeap, LargestIndex);
        true ->
            Heap
    end.

build_heap(L, 0) ->
    L;
build_heap(L, Index) ->
    NewL = max_heapify(L, Index),
    build_heap(NewL, Index - 1).

make_heap([]) ->
    [];
make_heap(L) ->
    build_heap(L, trunc(length(L) / 2)).

heap_pop([Head | Rest]) when  length(Rest) == 0 ->
    {Head, []};
heap_pop([Head | Rest]) ->
    {RestBody, RestTail} = lists:split(length(Rest) - 1, Rest),
    {Head, max_heapify(RestTail ++ RestBody, 1)}.

test_heap_pop([]) ->
    done;
test_heap_pop(Heap) ->
    {P, H} = heap_pop(Heap),
    io:format("~w, ~w~n", [P, H]),
    test_heap_pop(H).

adjust_heap_node(Heap, Index) when trunc(Index / 2) == 0 ->
    Heap;
adjust_heap_node(Heap, Index) ->
    IndexValue = lists:nth(Index, Heap),
    ParentIndex = trunc(Index / 2),
    ParentValue = lists:nth(ParentIndex, Heap),

    if
        IndexValue > ParentValue ->
            NewHeap = exchange(Heap, Index, IndexValue, ParentIndex,
ParentValue, 1),
            adjust_heap_node(NewHeap, ParentIndex);
        true ->
            Heap
    end.

heap_push(Heap, Push) ->
    adjust_heap_node(Heap ++ [Push], length(Heap) + 1).

-- 
Victory won't come to me, unless I go to it.



More information about the erlang-questions mailing list