[erlang-questions] Mnesia sorting/limiting

[Richard O'Keefe]

On 10 Jun 2009, at 8:30 pm, Ola Andersson A wrote:

> I was surprised to discover that there is no priority queue
> implementation in OTP.

You will find an implementation of skew heaps in
http://erlang.org/pipermail/erlang-questions/2007-August/028769.html

It was on the first page of results from a Google search for
(priority queues Erlang).

According to that thread as stored at Nabble, the use of gb_trees
for priority queues was proposed by Ulf Wiger.

There is a paper "Optimal Purely Functional Priority Queues" by
Brodal and Okasaki at
http://www.brics.dk/RS/96/37/BRICS-RS-96-37.pdf
which it might be interesting to translate into Erlang; that
paper uses ML, which is strict like Erlang, not lazy like Haskell.
However, I'd draw your attention to a sentence in that paper:
"Our data structure is reasonably ecient in practice;
however, there are several competing data structures that, although
not asymptotically optimal, are somewhat faster than ours in practice."

We had a visitor here for a month or two a couple of years ago who
was interested in priority queue algorithms.  He was evalluating a
recent theoretically improved algorithm, and was quite pleased that
his implementation of it was _by actual measurement_ faster than
several other moderately recent contenders.  I said "why aren't
you including the old heap-in-an-array data structure in your
benchmarks?  I think you really OUGHT to include the old heap-in-
an-array data structure in your benchmarks!"  So he did.  And it
was about 10 times faster than the _theoretically_ better ones.

If all you need is new(), empty(), insert(), find_min(), and
remove_min(), something like skew heaps or perfectly balanced
heaps will probably be hard to beat.  If you need fancier things
like O(1) meld(), then you will need something like the
Brodal/Okasaki data structure.