[erlang-questions] [ANN] Priority Queue Implementation

[Ulf Wiger]

I'm partial to skew heaps, mainly because they are so elegant.

http://www.cse.yorku.ca/~andy/courses/4101/lecture-notes/LN5.pdf

Something like this (although I've done only basic testing):

-module(skew).
-export([new/0, in/2, out/1]).

new() ->
    [].

in(X, Heap) ->
    merge({X,[],[]}, Heap).

out([]) ->
    error;
out({X, L, R}) ->
    {X, merge(L, R)}.

merge({P0,Pl,Pr}, {Q0,_,_} = Q) when P0 < Q0 ->
    {P0, Pr, merge(Pl,Q)};
merge({P0,_,_} = P, {Q0,Ql,Qr}) when P0 > Q0 ->
    {Q0, Qr, merge(Ql,P)};
merge({P0,Pl,Pr} = P,{P0,Ql,Qr}) ->   % equal roots
    merge(P, merge(merge(Pl,Pr), merge(Ql,Qr)));
merge([], Q) -> Q;
merge(P, []) -> P.

The cost is amortized O(log N) for in/2 and out/1. For peeking at the min, it's O(1).

BR,
Ulf W

On 9 Nov 2011, at 04:33, Michael Truog wrote:

> I was looking at Erlang priority queue implementations and the Riak/RabbitMQ one seemed a bit slow.  I have a different implementation with the same API here: https://github.com/okeuday/pqueue/blob/master/src/pqueue.erl
> 
> The results from my test are here: http://okeuday.livejournal.com/19187.html
> 
> The implementation has "in" operations that are roughly 3 times faster (300%), however, the "out" operation became roughly 30% slower.  So, as long as the priority queue is storing a decent amount of items, this data structure should provide better speed.  The implementation is limited to a specific priority range: -20 (high) to 20 (low).
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions

Ulf Wiger, CTO, Erlang Solutions, Ltd.
http://erlang-solutions.com



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20111109/4d4147a3/attachment.htm>