[erlang-questions] [ANN] Priority Queue Implementation

[Hynek Vychodil]

You can achieve this simply using {Priority, Order, Value} or
{Priority, now(), Value} i.e. you can do it by wrapping mine pair_heap
implementation to very simple wrapper.

new() -> {0, pair_heap:new()}.

in(Priority, Value, {Count, Q}) ->
  {Count+1, pair_heap:insert({Priority, Count, Value}, Q)}.

out({Count, Q}) ->
  case pair_heap:find_min(Q) of
    {_,_,Value} -> {Value, {Count, pair_heap:delete(Q)}};
    empty -> empty
  end.

If you need biggest priority first you can change

in(Priority, Value, {Count, Q}) ->
  {Count+1, pair_heap:insert({-Priority, Count, Value}, Q)}.

There is not need make special priority implementation in Erlang.

On Sat, Nov 12, 2011 at 6:06 AM, Michael Truog <mjtruog@REDACTED> wrote:
> I was looking for a priority queue implementation where the priority is separate from the value being queued, where the order is preserved for the same priority.  That might not be a typical application of a heap to a priority queue, because it might be expected to lose order within the heap structure.  Since I want the priority to be separate from the value, the data structure I am trying to pursue is a bit different.
>
> On 11/11/2011 09:08 AM, Hynek Vychodil wrote:
>> 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