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 α 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.