Heap.md

Heap

Class Heap<X> provides a priority queue of elements of type X.

The class wraps a purely-functional implementation based on a leftist heap.

Note on the constructor: The constructor takes in a comparison function compare that defines the ordering between elements of type X. Most primitive types have a default version of this comparison function defined in their modules (e.g. Nat.compare). The runtime analysis in this documentation assumes that the compare function runs in O(1) time and space.

Example:

import Heap "mo:base/Heap";
import Text "mo:base/Text";

let heap = Heap.Heap<Text>(Text.compare);

Runtime: O(1)

Space: O(1)

Type Tree

type Tree<X> = ?(Int, X, Tree<X>, Tree<X>)

Class Heap<X>

class Heap<X>(compare : (X, X) -> O.Order)

Function put

func put(x : X)

Inserts an element into the heap.

Example:

heap.put("apple");
heap.peekMin() // => ?"apple"

Runtime: O(log(n))

Space: O(log(n))

Function peekMin

func peekMin() : ?X

Return the minimal element in the heap, or null if the heap is empty.

Example:

heap.put("apple");
heap.put("banana");
heap.put("cantaloupe");
heap.peekMin() // => ?"apple"

Runtime: O(1)

Space: O(1)

Function deleteMin

func deleteMin()

Delete the minimal element in the heap, if it exists.

Example:

heap.put("apple");
heap.put("banana");
heap.put("cantaloupe");
heap.deleteMin();
heap.peekMin(); // => ?"banana"

Runtime: O(log(n))

Space: O(log(n))

Function removeMin

func removeMin() : (minElement : ?X)

Delete and return the minimal element in the heap, if it exists.

Example:

heap.put("apple");
heap.put("banana");
heap.put("cantaloupe");
heap.removeMin(); // => ?"apple"

Runtime: O(log(n))

Space: O(log(n))

Function share

func share() : Tree<X>

Return a snapshot of the internal functional tree representation as sharable data. The returned tree representation is not affected by subsequent changes of the Heap instance.

Example:

heap.put("banana");
heap.share();

Useful for storing the heap as a stable variable, pretty-printing, and sharing it across async function calls, i.e. passing it in async arguments or async results.

Runtime: O(1)

Space: O(1)

Function unsafeUnshare

func unsafeUnshare(tree : Tree<X>)

Rewraps a snapshot of a heap (obtained by share()) in a Heap instance. The wrapping instance must be initialized with the same compare function that created the snapshot.

Example:

heap.put("apple");
heap.put("banana");
let snapshot = heap.share();
let heapCopy = Heap.Heap<Text>(Text.compare);
heapCopy.unsafeUnshare(snapshot);
heapCopy.peekMin() // => ?"apple"

Useful for loading a stored heap from a stable variable or accesing a heap snapshot passed from an async function call.

Runtime: O(1).

Space: O(1).

Function fromIter

func fromIter<X>(iter : I.Iter<X>, compare : (X, X) -> O.Order) : Heap<X>

Returns a new Heap, containing all entries given by the iterator iter. The new map is initialized with the provided compare function.

Example:

let entries = ["banana", "apple", "cantaloupe"];
let iter = entries.vals();

let newHeap = Heap.fromIter<Text>(iter, Text.compare);
newHeap.peekMin() // => ?"apple"

Runtime: O(size)

Space: O(size)