HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

ModulePSQueue-1.2.2Haskell2010

Data.PSQueue

A priority search queue (henceforth queue) efficiently supports the operations 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.

  • 2 types
  • 29 values
  • PackagePSQueue-1.2.2
  • Exports31
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourcePSQueue.hs

Binding Type

3 declarations
datadata Binding k p
#

k :-> p binds the key k with the priority p.

Constructors

Instances4Eq, Ord, Read, Show
  • (Eq k, Eq p) => Eq (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
  • (Ord k, Ord p) => Ord (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
  • (Read k, Read p) => Read (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
  • (Show k, Show p) => Show (Binding k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
valueprio :: Binding k p -> p
#

The priority of a binding

Priority Search Queue Type

1 declaration
datadata PSQ k p
#

A mapping from keys k to priorites p.

Instances2Eq, Show
  • (Eq k, Eq p) => Eq (PSQ k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal
  • (Show k, Show p) => Show (PSQ k p)Defined in PSQueue-1.2.2 · Data.PSQueue.Internal

Query

3 declarations
valuesize :: PSQ k p -> Int
#

O(1) The number of bindings in a queue.

valuenull :: PSQ k p -> Bool
#

O(1) True if the queue is empty.

valuelookup :: Ord k => k -> PSQ k p -> Maybe p
#

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

Construction

2 declarations
valuesingleton :: k -> p -> PSQ k p
#

O(1) Build a queue with one binding.

Insertion

2 declarations
valueinsert :: (Ord k, Ord p) => k -> p -> PSQ k p -> PSQ k p
#

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

valueinsertWith
  1. :: (Ord k, Ord p)
  2. => p -> p -> p
  3. -> k
  4. -> p
  5. -> PSQ k p
  6. -> PSQ k p
#

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

Delete/Update

6 declarations
valuedelete :: (Ord k, Ord p) => k -> PSQ k p -> PSQ k p
#

O(log n) Remove a binding from the queue.

valueadjust :: (Ord p, Ord k) => (p -> p) -> k -> PSQ k p -> PSQ k p
#

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

valueupdate :: (Ord k, Ord p) => (p -> Maybe p) -> k -> PSQ k p -> PSQ k p
#

O(log n) The expression (update f k q) updates the priority p bound k (if it is in the queue). If (f p) is Nothing, the binding is deleted. If it is (Just z), the key k is bound to the new priority z.

valueupdateWithKey
  1. :: (Ord k, Ord p)
  2. => k -> p -> Maybe p
  3. -> k
  4. -> PSQ k p
  5. -> PSQ k p
#

O(log n). The expression (updateWithKey f k q) updates the priority p bound k (if it is in the queue). If (f k p) is Nothing, the binding is deleted. If it is (Just z), the key k is bound to the new priority z.

valuealter :: (Ord k, Ord p) => (Maybe p -> Maybe p) -> k -> PSQ k p -> PSQ k p
#

O(log n). The expression (alter f k q) alters the priority p bound to k, or absence thereof. alter can be used to insert, delete, or update a priority in a queue.

Conversion

7 declarations
valuekeys :: PSQ k p -> [k]
#

O(n) The keys of a priority queue

valuetoAscList :: PSQ k p -> [Binding k p]
#

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

valuetoDescList :: PSQ k p -> [Binding k p]
#

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

valuefromAscList :: (Eq k, Ord p) => [Binding k p] -> PSQ k p
#

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.

valuefromDistinctAscList :: Ord p => [Binding k p] -> PSQ k p
#

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

5 declarations
valuedeleteMin :: Ord p => PSQ k p -> PSQ k p
#

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

valueminView :: Ord p => PSQ k p -> Maybe (Binding k p, PSQ k p)
#

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

valueatMost :: Ord p => p -> PSQ k p -> [Binding k p]
#

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
valueatMostRange :: (Ord k, Ord p) => p -> (k, k) -> PSQ k p -> [Binding k p]
#

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'

Fold

2 declarations
valuefoldr :: (Binding k p -> b -> b) -> b -> PSQ k p -> b
#

Right fold over the bindings in the queue, in key order.

valuefoldl :: (b -> Binding k p -> b) -> b -> PSQ k p -> b
#

Left fold over the bindings in the queue, in key order.