Copyright | (c) Ross Paterson 2008 |
---|---|

License | BSD-style |

Maintainer | ross@soi.city.ac.uk |

Stability | experimental |

Portability | non-portable (MPTCs and functional dependencies) |

Safe Haskell | Safe-Inferred |

Language | Haskell98 |

Min-priority queues implemented using the `FingerTree`

type,
following section 4.6 of

- Ralf Hinze and Ross Paterson,
"Finger trees: a simple general-purpose data structure",
*Journal of Functional Programming*16:2 (2006) pp 197-217. http://staff.city.ac.uk/~ross/papers/FingerTree.html

These have the same big-O complexity as skew heap implementations,
but are approximately an order of magnitude slower.
On the other hand, they are stable, so they can be used for fair
queueing. They are also shallower, so that `fmap`

consumes less
space.

An amortized running time is given for each operation, with *n*
referring to the size of the priority queue. These bounds hold even
in a persistent (shared) setting.

*Note*: Many of these operations have the same names as similar
operations on lists in the Prelude. The ambiguity may be resolved
using either qualification or the `hiding`

clause.

- data PQueue k v
- empty :: Ord k => PQueue k v
- singleton :: Ord k => k -> v -> PQueue k v
- union :: Ord k => PQueue k v -> PQueue k v -> PQueue k v
- insert :: Ord k => k -> v -> PQueue k v -> PQueue k v
- add :: Ord k => k -> v -> PQueue k v -> PQueue k v
- fromList :: Ord k => [(k, v)] -> PQueue k v
- null :: Ord k => PQueue k v -> Bool
- minView :: Ord k => PQueue k v -> Maybe (v, PQueue k v)
- minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v)

# Documentation

Priority queues.

# Construction

fromList :: Ord k => [(k, v)] -> PQueue k v Source

*O(n)*. Create a priority queue from a finite list of priorities
and values.

# Deconstruction

minViewWithKey :: Ord k => PQueue k v -> Maybe ((k, v), PQueue k v) Source

*O(1)* for the element, *O(log(n))* for the reduced queue.
Returns `Nothing`

for an empty map, or the minimal (priority, value)
pair together with the rest of the priority queue.

`minViewWithKey`

`empty`

=`Nothing`

`minViewWithKey`

(`singleton`

k v) =`Just`

((k, v),`empty`

)- If

and`minViewWithKey`

qi =`Just`

((ki, vi), qi')`k1 <= k2`

, then`minViewWithKey`

(`union`

q1 q2) =`Just`

((k1, v1),`union`

q1' q2) - If

and`minViewWithKey`

qi =`Just`

((ki, vi), qi')`k2 < k1`

, then`minViewWithKey`

(`union`

q1 q2) =`Just`

((k2, v2),`union`

q1 q2')