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 'a t
type 'a pq = 'a t

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

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

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

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

Substructures

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

Types

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

Values

val empty : unit → 'a pq
Construct the empty priority queue.
val singleton : (Key.t * 'a) → 'a pq
(singleton (k, v)) evaluates to the priority queue containing only the pair $(k, v)$.
val fromList : (Key.t * 'a) list → 'a pq
Construct the priority queue containing all key-value pairs from a list.
val size : 'a pq → int
Return the number of key-value pairs in a priority queue.
val findMin : 'a pq → (Key.t * 'a) 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 : 'a pq * (Key.t * 'a) → 'a pq
Insert one key-value pair into a priority queue.
val deleteMin : 'a pq → (Key.t * 'a) option * 'a 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 : 'a pq * 'a pq → 'a pq
(meld (x, y)) evalautes to the priority queue which contains all key-value pairs from both $x$ and $y$.
val $ : (Key.t * 'a) → 'a pq
An alias for singleton.
val % : (Key.t * 'a) list → 'a pq
An alias for fromList.