The PQ signature

« 210 Library Documentation

Overview

A priority queue is a collection of key-value pairs which prioritizes access to its minimum key. The key type is ordered and fixed by the Key substructure while the value type is polymorphic.

Interface

structure Key : ORDKEY

type α t
type α pq = α t

val empty : unit → α pq
val singleton : (Key.t * α) → α pq
val fromList : (Key.t * α) list → α pq

val size : α pq → int
val findMin : α pq → (Key.t * α) option

val insert : α pq * (Key.t * α) → α pq
val deleteMin : α pq → (Key.t * α) option * α pq
val meld : α pq * α pq → α pq

val $ : (Key.t * α) → α pq
val % : (Key.t * α) list → α pq

Substructures

structure Key : ORDKEY
The Key substructure defines the key type of priority queues, providing comparison and other useful functions.

Types

type α t
The abstract priority queue type.
type α pq = α t
An alias for α t, for readability.

Values

val empty : unit → α pq
Construct the empty priority queue.
val singleton : (Key.t * α) → α pq
(singleton (k, v)) evaluates to the priority queue containing only the pair $(k, v)$.
val fromList : (Key.t * α) list → α pq
Construct the priority queue containing all key-value pairs from a list.
val size : α pq → int
Return the number of key-value pairs in a priority queue.
val findMin : α pq → (Key.t * α) option
Return the minimum key (paired with its associated value) in a priority queue, or NONE if the queue is empty. If there are multiple minimum keys, then any one of them might be chosen.
val insert : α pq * (Key.t * α) → α pq
Insert one key-value pair into a priority queue.
val deleteMin : α pq → (Key.t * α) option * α pq
(deleteMin q) evaluates to $(x, q')$ where $x$ is the minimum key (paired with its associated value) in $q$, and $q'$ is the priority queue which contains all elements of $q$ except for $x$. If there are multiple minimum keys in $q$, then any one of them might be chosen. If $q$ is empty, then $x$ = NONE and $q' = q$.
val meld : α pq * α pq → α pq
(meld (x, y)) evalautes to the priority queue which contains all key-value pairs from both $x$ and $y$.
val $ : (Key.t * α) → α pq
An alias for singleton.
val % : (Key.t * α) list → α pq
An alias for fromList.