[erlang-questions] Priority queues and Erlang

[Ulf Wiger]

John Haugeland wrote:
> 
> It is possible through skew binomial queues to achieve better
> theoretical growth cases than the trees have, but the linear overhead
> is so large that you're talking several tens of gigabytes before they
> become even remotely competitive.

So at least skew heaps are cute (like bubble sort perhaps).

Here's an Erlang implementation of a skew heap, along the
lines of Chapter 1, Fun with binary heaps (Chris Okasaki)
from:

http://www.palgrave.com/PDFs/0333992857.Pdf:

This particular version implements a "round-robin heap"
(Chapter 1.4). Inserting and removing elements take
amortized O(log N) time. Finding the smallest element,
without removing it, is - trivially - O(1).

Not making any claims or challenging yours, but I thought
it might be nice to offer an illustration to go along with
the discussion. One minor note, perhaps, would be that Okasaki
mentions /persistent/ vs /ephemeral/ data structures, which
would correspond to mutable vs immutable, and states that
/most/ imperative implementations use ephemeral data structures
(chapter 1.3.)

(BTW, watching John Hughes solve exercise 1.5 using QuickCheck
once, was what triggered me to invite him to do a QuickCheck
pilot at Ericsson.)

-module(skew).
-compile(export_all).

-define(null, []).

empty() ->
     ?null.

is_empty(?null) -> true;
is_empty({_,_,_}) -> false.


in(X, ?null) -> {X,?null, ?null};
in(X, A) -> merge({X,?null, ?null}, A).

%% out(Heap) -> {min(Heap), deleteMin(Heap)}.
%%
out({X,A,B}) -> {X, merge(A,B)}.

min({X,_,_}) -> X.

deleteMin({_, A, B}) -> merge(A, B).

merge(A, ?null) -> A;
merge(?null, B) -> B;
merge({Xa,_,_}=A, {Xb,_,_}=B) when Xa =< Xb ->
     join(A, B);
merge(A, B) ->
     join(B, A).

join({X,A,B}, C) ->
     {X,B,merge(A,C)}.

BR,
Ulf W
-- 
Ulf Wiger
CTO, Erlang Training & Consulting Ltd
http://www.erlang-consulting.com