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

Pierpaolo Bernardi <>
Thu Aug 30 18:17:04 CEST 2007

```On 8/30/07, Jeffrey Chen <> 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  :  <>
%%% Description : Skew heaps
%%% Created : 30 May 2003 by Pierpaolo BERNARDI <>

-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.

```