(std mutable heap)

Reference

Overview

Priority queue backed directly by .NET PriorityQueue<T,P>, ordered with smallest priority first.

(import (std mutable heap))

(def tasks (mutableheap))
(mutableheap-add! tasks "write" 2)
(mutableheap-add! tasks "plan" 1)
(mutableheap-add! tasks "test" 3)
(mutableheap-peek tasks)   ; (Some (Tuple "plan" 1))
(mutableheap-pop! tasks)   ; (Some (Tuple "plan" 1))
(mutableheap-pop! tasks)   ; (Some (Tuple "write" 2))

;; Max-heap (largest priority first): invert the comparison
(def big-first (mutableheap-by (fun (a b) (compare b a))))

(MutableHeap a p) aliases .NET PriorityQueue<T,P> directly. It is implemented as an array-backed 4-ary min-heap. Enqueue (add!) and dequeue (pop!) operations run in O(log n) time. Peeking the top element runs in O(1) time. Foreign interop via import/extern accepting PriorityQueue<T,P> accepts MutableHeap directly.

Elements and priorities. (mutableheap-add! h task 3) adds task with priority 3. The heap orders priorities, not elements; the element type does not require an Ord instance. Peeking and popping return the element and its priority together as a (Tuple a p).

Min-heap semantics. Elements with the lowest priority value are dequeued first. To construct a max-heap (highest priority first), pass a reversed comparison to mutableheap-by. Elements with identical priorities are dequeued in non-deterministic order.

Priority comparers. Constructors mutableheap, seq->mutableheap, and list->mutableheap use .NET’s default comparer, Comparer<P>.Default. For Bjolang types with an Ord instance, this resolves to that instance. If no comparer exists for the type, the first comparison raises an exception. Use mutableheap-by to supply a custom comparison function.

Empty heap behavior. Peeking or popping an empty heap returns None without raising exceptions.

Unordered traversals. Priority queues do not support ordered in-place iteration because sorting requires destructive dequeue operations. mutableheap->unordered-seq and mutableheap->unordered-list expose internal storage without sorting.

Equality. Heaps do not implement structural Eq; equality checks compare reference identity.

Thread safety. Heaps are not thread-safe. Concurrent modifications require external synchronization.

Traits. Implements Collection over (Tuple a p), Written and Displayed.

See also: MutableHeap, mutableheap, mutableheap-by, mutableheap-add!, mutableheap-pop!

Reference

Types

Functions

Types

MutableHeap

type alias ↑ Types

Priority queue of %a with priorities %p (aliases .NET PriorityQueue<T,P>).

%a
The element type (does not require Ord).
%p
The priority type (lowest priority dequeued first).

See also: mutableheap, mutableheap-by

Functions

mutableheap

function ↑ Functions

(: mutableheap (-> (MutableHeap %a %p)))

Creates an empty min-heap using default priority ordering.

returns
A new empty heap using Comparer<P>.Default.

See also: mutableheap-by

mutableheap-by

function ↑ Functions

(: mutableheap-by (-> (-> %p %p int) (MutableHeap %a %p)))

Creates an empty min-heap using a custom priority comparison function.

cmp
Comparison function returning negative if a < b, 0 if equal, and positive if a > b.
returns
A new empty heap.
(mutableheap-by (fun (a b) (compare a b)))   ; min-heap using Ord
(mutableheap-by (fun (a b) (compare b a)))   ; max-heap

See also: mutableheap, mutableheap-copy

mutableheap-length

function ↑ Functions

(: mutableheap-length (-> (MutableHeap %a %p) int))

Returns the number of elements in the heap.

h
The heap.
returns
The element count.

See also: mutableheap-empty?

mutableheap-empty?

function ↑ Functions

(: mutableheap-empty? (-> (MutableHeap %a %p) bool))

Tests if the heap contains no elements.

h
The heap.
returns
#t if empty, otherwise #f.

See also: mutableheap-length

mutableheap-clear!

function ↑ Functions

(: mutableheap-clear! (-> (MutableHeap %a %p) void))

Removes all elements from the heap, retaining priority order.

h
The heap to clear.

mutableheap-add!

function ↑ Functions

(: mutableheap-add! (-> (MutableHeap %a %p) %a %p void))

Enqueues an element with the given priority.

h
The heap to modify.
x
The element to add.
priority
The element's priority.

Runs in O(log n) time.

See also: mutableheap-add-all!, mutableheap-add-pop!, mutableheap-pop!

mutableheap-add-all!

function ↑ Functions

(: mutableheap-add-all! (-> (MutableHeap %a %p) (Seq (Tuple %a %p)) void))

Enqueues all element-priority pairs from a sequence.

h
The heap to modify.
xs
Sequence of (Tuple element priority) pairs to add.

See also: mutableheap-add!

mutableheap-add-pop!

function ↑ Functions

(: mutableheap-add-pop! (-> (MutableHeap %a %p) %a %p %a))

Enqueues an element and removes the minimum element in a single pass.

h
The heap to modify. Length remains unchanged.
x
The element to add.
priority
The priority for x.
returns
The removed minimum element. If the heap was empty or priority was already minimum, returns x directly.
;; Keep the top 10 scores in a fixed-size heap:
(if (< (mutableheap-length top) 10)
    (mutableheap-add! top name score)
    (ignore (mutableheap-add-pop! top name score)))

Performs the enqueue and dequeue in a single rebalancing pass, avoiding the overhead of consecutive add and pop calls.

See also: mutableheap-add!, mutableheap-pop!

mutableheap-peek

function ↑ Functions

(: mutableheap-peek (-> (MutableHeap %a %p) (out %a) (out %p) (Option (Tuple %a %p))))

Returns the element with minimum priority without removing it, or None if empty.

h
The heap to inspect.
returns
(Some (Tuple element priority)) for the minimum entry, or None if empty.

See also: mutableheap-pop!

mutableheap-pop!

function ↑ Functions

(: mutableheap-pop! (-> (MutableHeap %a %p) (out %a) (out %p) (Option (Tuple %a %p))))

Removes and returns the element with minimum priority, or None if empty.

h
The heap to modify.
returns
(Some (Tuple element priority)) for the minimum entry, or None if empty.
;; Dequeue tasks in priority order:
(let loop ()
  (match (mutableheap-pop! tasks)
    (None unit)
    ((Some (Tuple task _)) (run task) (loop))))

Runs in O(log n) time.

See also: mutableheap-peek, mutableheap-add!

mutableheap-copy

function ↑ Functions

(: mutableheap-copy (-> (MutableHeap %a %p) (MutableHeap %a %p)))

Creates a shallow copy of the heap preserving elements and comparer.

h
The heap to copy.
returns
A new heap with identical elements and ordering.

Retains the priority comparer of the source heap.

list->mutableheap

function ↑ Functions

(: list->mutableheap (-> (List (Tuple %a %p)) (MutableHeap %a %p)))
(list->mutableheap xs)

Constructs a new heap from a list of element-priority pairs.

xs
List of (Tuple element priority) pairs.
returns
A new heap using default priority ordering.

See also: mutableheap->unordered-list, seq->mutableheap

mutableheap->unordered-list

function ↑ Functions

(: mutableheap->unordered-list (-> (MutableHeap %a %p) (List (Tuple %a %p))))
(mutableheap->unordered-list h)

Converts the heap to an unordered list of element-priority pairs.

h
The source heap.
returns
A new list of (Tuple element priority) pairs in arbitrary order.

See also: list->mutableheap, mutableheap-pop!

seq->mutableheap

function ↑ Functions

(: seq->mutableheap (-> (Seq (Tuple %a %p)) (MutableHeap %a %p)))

Constructs a new heap from a sequence of element-priority pairs.

xs
Sequence of (Tuple element priority) pairs.
returns
A new heap using default priority ordering.

To construct a heap with a custom comparer, initialize with mutableheap-by and populate using mutableheap-add-all!.

See also: mutableheap->unordered-seq, mutableheap-add-all!

mutableheap->unordered-seq

function ↑ Functions

(: mutableheap->unordered-seq (-> (MutableHeap %a %p) (Seq (Tuple %a %p))))

Views the heap as a sequence of element-priority pairs in arbitrary order.

h
The source heap.
returns
A Seq of (Tuple element priority) pairs without sorting.

Iterates directly over internal heap storage. Mutating the heap during traversal can raise System.InvalidOperationException. To consume elements in priority order, call mutableheap-pop! repeatedly.

See also: seq->mutableheap, mutableheap->unordered-list

mutableheap->str

function ↑ Functions

(: mutableheap->str (-> (MutableHeap %a %p) string))
(mutableheap->str h)

Deprecated: use displayed. Formats the heap as text in the form #mheap(x priority …).

h
The heap to format.
returns
Formatted string representation displaying elements and priorities in storage order.
(displayed (list->mutableheap (list (Tuple 7 1))))   ; "#mheap(7 1)"

The same text as displayed gives for a heap. Note that elements appear in internal storage order rather than priority order.