[erlang-questions] How can I implement a priority queue with Erlang?

David Mercer <>
Thu Aug 30 16:48:59 CEST 2007


On Thursday, August 30, 2007 at 07:34, Jeffrey Chen wrote:
> I'm trying to implement a priority queue using heap struct. But I
> can't do that efficient. Can anybody help me? I'll post my code below.

I'm thinking heap structures are not going to be very efficient in Erlang.
Not having looked at your code in particular, but if I recall correctly,
heaps are efficient when you have random access into an array.  In Erlang,
you'll be doing a lot of list traversals to get to the nth element, and to
switch elements, etc.  It would be more efficient simply to do a single scan
of the list and insert the element in the appropriate place.  Or use gb_tree
(or some other tree structure) to help.  They are going to be more efficient
than a linear list implementing a heap.

Cheers,

David





More information about the erlang-questions mailing list