Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

Re: Data Structure needed for Event Queue

by Zaxo (Archbishop)
on May 27, 2002 at 21:01 UTC ( #169645=note: print w/replies, xml ) Need Help??

in reply to Data Structure needed for Event Queue

Anonymonk has the right idea, though his link to Heap is busted. Also see replies to looking for a Priority Queue, where tachyon exhibits an implementation.

After Compline,

  • Comment on Re: Data Structure needed for Event Queue

Replies are listed 'Best First'.
Re: Re: Data Structure needed for Event Queue
by educated_foo (Vicar) on May 27, 2002 at 21:48 UTC
    Like a number of others in the monastery, I would suggest you not use Heap. This may be one of those rare cases where it's faster and more reliable to write and debug your own version than go to CPAN. Alternatively, the authors of "Elements of Programming with Perl" have been kind enough to put a kinder, gentler implementation on the web. I haven't tested it, but it's at least simple enough that it's possible to read and understand the code, and relatively painless to use it.


      Just curious, but without my references im not really sure but what kind of heap is that? Fibonnacci?

      Yves / DeMerphq
      Writing a good benchmark isnt as easy as it might look.

        Just curious, but without my references im not really sure but what kind of heap is that? Fibonnacci?

        Assuming you are referring to the EoPwP heap that educated_foo points to, then (as stated by educated_foo, who refers to me in the plural :-) it is strictly a simple, array-based implementation of a binary heap. It isn't documented except as it is built in the book.

        A main difference between this and the Heap model is that this one contains the comparison routines internally and works on the model of selecting a comparison method on heap creation and supplying a suitable key and satellite data for each inserted element (it is easy to use any objects for which you can supply a key) --- to use objects with the Heap version you need all of your objects to supply their own cmp() method for comparing themselves with any other object type in the heap. The latter is more flexible because the comparison routines may be arbitrarily complex, but does require that all your objects either inherit or supply their own common comparison method.

        Which "that"? Heap implements normal ("binary"), binomial, and fibonnacci heaps. The "Elements of" version is a normal binary heap.


Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://169645]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2022-05-25 17:41 GMT
Find Nodes?
    Voting Booth?
    Do you prefer to work remotely?

    Results (90 votes). Check out past polls.