[erlang-questions] [ANN] Priority Queue Implementation
Sat Nov 12 06:06:30 CET 2011
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:
> -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() -> ;
> 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
>> 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
>> erlang-questions mailing list
More information about the erlang-questions