[erlang-questions] [ANN] Priority Queue Implementation

[Hynek Vychodil]

I have used this pretty raw but simple priority queue implementation
for mine primes generation with true sieve:

-module(pair_heap).

-compile(inline).

-export([new/0, insert/2, find_min/1, delete_min/1, merge/2, to_list/1,
    from_list/1, insert_list/2]).

new() -> [].

find_min([H|_]) -> H;
find_min([]) -> empty.

%insert(E, H) -> merge([E], H).
insert(E, []) -> [E];
insert(E, [EH|SH]) when EH < E -> [EH|[[E]|SH]];
insert(E, [_|_]=H) -> [E|[H]].

merge([EA|_]=A, [EB|SB]) when EB < EA -> [EB|[A|SB]];
merge([EA|SA], [_|_]=B) -> [EA|[B|SA]];
merge([], B) -> B;
merge(A, []) -> A.

delete_min([]) -> [];
delete_min([_|SH]) ->
  merge_pairs(SH).

merge_pairs([]) -> [];
merge_pairs([X]) -> X;
merge_pairs([A,B|T]) -> merge(merge(A,B), merge_pairs(T)).

to_list([]) -> [];
to_list(H) -> [find_min(H) | to_list(delete_min(H))].

from_list([]) -> [];
from_list(L) -> insert_list(L, new()).

insert_list([E|T], H) -> insert_list(T, insert(E, H));
insert_list([], H) -> H.

It worked pretty well and fast for mine purposes.

On Fri, Nov 11, 2011 at 4:42 PM, Jesper Louis Andersen
<jesper.louis.andersen@REDACTED> wrote:
> On Thu, Nov 10, 2011 at 09:12, Michael Truog <mjtruog@REDACTED> wrote:
>> I previously added code that took care of that case, where two nodes needed
>> to be merged that both have queues.  However, I convinced myself at the
>> time, that the case would never happen.  So, the code probably needs to be
>> thought-through a bit more with more testing, but my hope is that merging
>> the queues isn't necessary.
>
> I have tested (tasted, but my typo was funnier) the forbidden fruit
> that is QuickCheck/PropEr. Your repository now has a pull-request in
> which I add partial testing via proper_statem. It generates an
> internal crash of the data structure code if we makes a bunch of
> inserts and then call len(), see
>
> https://github.com/okeuday/pqueue/issues/4
>
> Only your pqueue2 implementation is affected. pqueue is not shown to
> have any errors (yet). The crash is naturally in the "merge" part of the code :P
>
> --
> J.
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>



-- 
Hynek Vychodil
BI consultant

GoodData
náměstí 28. října 1104/17, 602 00, Brno - Černá Pole
Office:   +420 530 50 7704
E-mail:  hynek@REDACTED
Web:     www.gooddata.com