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

[Pierpaolo Bernardi]

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.

For priority queues, I use the one below.

HTH

P.

%%% File    : skew.erl
%%% Author  :  <olopierpa@REDACTED>
%%% Description : Skew heaps
%%% Created : 30 May 2003 by Pierpaolo BERNARDI <olopierpa@REDACTED>

-module(skew).

-export([empty/0,
	 is_empty/1,
	 min/1,
	 delete_min/1,
	 insert/2,
	 merge/2
	 ]).


%% Aggressive inlining - will increase code size.
%%-compile(inline).
%%-compile({inline_size,100}).

%%-define(TESTING,true).

-ifdef(TESTING).
-compile(export_all).
-endif.

-define(THE_EMPTY_HEAP, the_empty_heap).

empty() ->
    ?THE_EMPTY_HEAP.

is_empty(?THE_EMPTY_HEAP) -> true;
is_empty(_) -> false.

min({X, _, _}) -> X.

delete_min({_X, A, B}) -> merge(A, B).

insert(X, A) ->
    merge({X, ?THE_EMPTY_HEAP, ?THE_EMPTY_HEAP}, A).

merge(A, ?THE_EMPTY_HEAP) ->
    A;
merge(?THE_EMPTY_HEAP, B) ->
    B;
merge({MA, LA, RA}, B={MB, _, _}) when MA =< MB ->
    {MA, RA, merge(LA, B)};
merge(A, {M, L, R}) ->
    {M, R, merge(L, A)}.


-ifdef(TESTING).

test() ->
    test(100000, 1, 1000000000).

test(N, Da, A) ->
    pblib:randomize(),
    Q = fa_random_heap(N, Da, A),
    scrivi_heap(Q).

misura() ->
    T0 = pblib:mo(),
    _Q = fa_random_heap(100000, 1, 1000000000),
    T1 = pblib:mo(),
    T1 - T0.

fa_random_heap(Quanti, Da, A) ->
    fa_random_heap(Quanti, Da, A, empty()).

fa_random_heap(0, _Da, _A, Q) ->
    Q;
fa_random_heap(N, Da, A, Q) ->
    fa_random_heap(N-1, Da, A, insert(random:uniform(A- Da+1)+Da-1, Q)).


fa_random_heap2(Quanti, Da, A) ->
    fa_random_heap2(Quanti, Da, A, empty()).

fa_random_heap2(0, _Da, _A, Q) ->
    Q;
fa_random_heap2(N, Da, A, Q) ->
    fa_random_heap2(N-1, Da, A, insert(1000000-N, Q)).

scrivi_heap(Q) ->
    case is_empty(Q) of
	true ->
	    ok;
	false ->
	    M = min(Q),
	    Q1 = delete_min(Q),
	    io:fwrite("~s\n", [pblib:ultospun(M)]),
	    scrivi_heap(Q1)
    end.

profo(?THE_EMPTY_HEAP) ->
    0;
profo({_, A, B}) ->
    1 + lists:max([profo(A),
		   profo(B)]).

dimen(?THE_EMPTY_HEAP) ->
    0;
dimen({_, A, B}) ->
    1 + dimen(A) + dimen(B).

-endif.