Safe Haskell | Safe-Infered |
---|

A *priority search queue* (henceforth *queue*) efficiently supports the
opperations of both a search tree and a priority queue. A `Binding`

is a
product of a key and a priority. Bindings can be inserted, deleted, modified
and queried in logarithmic time, and the binding with the least priority can be
retrieved in constant time. A queue can be built from a list of bindings,
sorted by keys, in linear time.

This implementation is due to Ralf Hinze.

- Hinze, R.,
*A Simple Implementation Technique for Priority Search Queues*, ICFP 2001, pp. 110-121

- data Binding k p = k :-> p
- key :: Binding k p -> k
- prio :: Binding k p -> p
- data PSQ k p
- size :: PSQ k p -> Int
- null :: PSQ k p -> Bool
- lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe p
- empty :: (Ord k, Ord p) => PSQ k p
- singleton :: (Ord k, Ord p) => k -> p -> PSQ k p
- insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p
- insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k p
- delete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p
- adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p
- adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k p
- update :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- updateWithKey :: (Ord k, Ord p) => (k -> p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p
- keys :: (Ord k, Ord p) => PSQ k p -> [k]
- toList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]
- fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- fromDistinctAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k p
- findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)
- deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k p
- minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)
- atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]
- atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]
- foldr :: (Ord k, Ord p) => (Binding k p -> b -> b) -> b -> PSQ k p -> b
- foldl :: (Ord k, Ord p) => (b -> Binding k p -> b) -> b -> PSQ k p -> b

# Binding Type

`k :-> p`

binds the key `k`

with the priority `p`

.

k :-> p |

# Priority Search Queue Type

A mapping from keys `k`

to priorites `p`

.

# Query

lookup :: (Ord k, Ord p) => k -> PSQ k p -> Maybe pSource

*O(log n)* The priority of a given key, or Nothing if the key is not
bound.

# Construction

# Insertion

insert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k pSource

*O(log n)* Insert a binding into the queue.

insertWith :: (Ord k, Ord p) => (p -> p -> p) -> k -> p -> PSQ k p -> PSQ k pSource

*O(log n)* Insert a binding with a combining function.

# Delete/Update

adjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k pSource

*O(log n)* Adjust the priority of a key.

adjustWithKey :: (Ord k, Ord p) => (k -> p -> p) -> k -> PSQ k p -> PSQ k pSource

*O(log n)* Adjust the priority of a key.

alter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k pSource

*O(log n)*. The expression (

) alters the priority `alter`

f k q`p`

bound to `k`

, or absence thereof.
alter can be used to insert, delete, or update a priority in a queue.

# Conversion

toAscList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]Source

*O(n)* Convert a queue to a list in ascending order of keys.

toDescList :: (Ord k, Ord p) => PSQ k p -> [Binding k p]Source

*O(n)* Convert a queue to a list in descending order of keys.

fromList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource

*O(n log n)* Build a queue from a list of bindings.

fromAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource

*O(n)* Build a queue from a list of bindings in order of
ascending keys. The precondition that the keys are ascending is not checked.

fromDistinctAscList :: (Ord k, Ord p) => [Binding k p] -> PSQ k pSource

*O(n)* Build a queue from a list of distinct bindings in order of
ascending keys. The precondition that keys are distinct and ascending is not checked.

# Priority Queue

findMin :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p)Source

*O(1)* The binding with the lowest priority.

deleteMin :: (Ord k, Ord p) => PSQ k p -> PSQ k pSource

*O(log n)* Remove the binding with the lowest priority.

minView :: (Ord k, Ord p) => PSQ k p -> Maybe (Binding k p, PSQ k p)Source

*O(log n)* Retrieve the binding with the least priority, and the rest of
the queue stripped of that binding.

atMost :: (Ord k, Ord p) => p -> PSQ k p -> [Binding k p]Source

*O(r(log n - log r)* `atMost p q`

is a list of all the bindings in `q`

with
priority less than `p`

, in order of ascending keys.
Effectively,

atMost p' q = filter (\(k:->p) -> p<=p') . toList

atMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]Source

*O(r(log n - log r))* `atMostRange p (l,u) q`

is a list of all the bindings in
`q`

with a priority less than `p`

and a key in the range `(l,u)`

inclusive.
Effectively,

` atMostRange p' (l,u) q = filter (\(k:->p) -> l<=k && k<=u ) . ``atMost`

p'