[erlang-questions] Priority queues and Erlang
Ulf Wiger
<>
Sun Jun 14 14:30:07 CEST 2009
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
More information about the erlang-questions
mailing list