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

[Arnaud Bailly]

Thanks a lot. Yes it helps!

Arnaud
On Sun, Mar 4, 2012 at 9:38 PM, Joey Adams <joeyadams3.14159 at gmail.com> wrote:
> On Sun, Mar 4, 2012 at 1:27 PM, Arnaud Bailly <arnaud.oqube at gmail.com> 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