The PQUEUE signature

Overview

A priority queue $Q$ is a finite collection of key value pairs that allows insertion of new pairs and lookup and deletion of the minimum key.

Interface

Substructures

structure Key : ORDKEY

The Key substructure defines the type of keys in a priority queue, providing equality, toString, and comparison functions on such elements.

Types

type 'a pq

This is the abstract type that represents a priority queue as described in the overview.

type key = Key.t

This indicates that the keys in a priority queue must be of type Key.t.

Values

val empty : unit -> 'a pq

(empty ()) evaluates to the empty priority queue.

val singleton : (key * 'a) -> 'a pq

(singleton (k, v)) evaluates to the priority queue containing only the element $(k, v)$.

val fromList : (key * 'a) list -> 'a pq

(fromList l) is the priority queue containing the items in $l$

val size : 'a pq -> int

(size Q) evaluates to $|Q|$, the number of elements in the priority queue $Q$.

val findMin : 'a pq -> (key * 'a) option

(findMin Q) evaluates to NONE if $|Q| = 0$ or SOME (k, v) where $k$ is the minimum key in $Q$, and $v$ is the value paired with that key. If there are multiple instances of the smallest key, the pair that is returned is arbitrary.

val insert : (key * 'a) -> 'a pq -> 'a pq

(insert (k, v) Q) evaluates to the priority queue $Q$ with $(k, v)$ added.

val deleteMin : 'a pq -> (key * 'a) option * 'a pq

(deleteMin k Q) evaluates to (NONE, Q) if $|Q| = 0$ or findMin Q and the priority queue $Q$ with the minimum removed otherwise.

val meld : 'a pq * 'a pq -> 'a pq

(meld (Q, R)) evaluates to the priority queue with all the elements in $Q$ and $R$.