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

[Ludovic Coquelle]

Sorry, I may not be able to help you with the code.

But I can point you to a very simple priority queue solution using gb_tree
proposed by Ulf Wiger:
http://www.erlang.org/pipermail/erlang-questions/2007-June/027585.html

I would be interested to know about has any other solutions.

On 8/30/07, Jeffrey Chen <bitcowboy@REDACTED> wrote:
>
> 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.
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20070830/d4ae80e8/attachment.htm>