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

[Joey Adams]

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