Re: [Haskell-cafe] Looking for an heap-like data structure allowing efficient update

Thanks a lot. Yes it helps! Arnaud On Sun, Mar 4, 2012 at 9:38 PM, Joey Adams wrote:

On Sun, Mar 4, 2012 at 1:27 PM, Arnaud Bailly wrote:

...

Hello Cafe, I am looking for a data structure that would have the following informal properties:  - allow efficient retrieval of minimum element for some ordering relation on a computed property of the elements  - allow efficient update of any element wrt to this property

I think what you're looking for is called a "priority search queue". It supports the operations of both a priority queue and a search tree.  Two implementations on Hackage are:

 * http://hackage.haskell.org/package/fingertree-psqueue

 * http://hackage.haskell.org/package/PSQueue

Both libraries appear to have the same API.  I'm not sure which of these is "better".  The priority search queue used by GHC's event manager is based on PSQueue.  On the other hand, fingertree-psqueue is newer.

In any case, a PSQ is just like a Map in that it binds keys to values.  The difference is that values are called "priorities", as you can efficiently look up or extract the minimum value.  Note that keys must be unique (just like with Map), but priorities do not need to be.

It appears that if you want to attach a "value" in addition to the priority, you'll need to define a data type.  E.g.:

   import Data.PSQueue (PSQ)    import Data.Unique (Unique)

   type Time = ... some efficient representation of time values ...

   data Event        = Event            { eventTimeout :: Time            , eventAction  :: IO ()            }

   instance Eq Event where        a == b = eventTimeout a == eventTimeout b

   instance Ord Event where        compare a b = compare (eventTimeout a) (eventTimeout b)

   type EventQueue = PSQ Unique Event

In this case, the PSQ will be able to remove the Event whose expiration is soonest.  It will also be able to remove an Event by its Unique key, useful for canceling Events.

Hope this helps, -Joey