The PQ signature

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.