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 Constructor details
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:
motoko name=initialize
import Heap "mo:base/Heap";
import Text "mo:base/Text";
let heap = Heap.Heap<Text>(Text.compare);
| Runtime | Space |
|-----------|-----------|
| O(1)
| O(1)
|
public func put(x : X)
Inserts an element into the heap.
Example:
motoko include=initialize
heap.put("apple");
heap.peekMin() // => ?"apple"
| Runtime | Space |
|-----------|-----------|
| O(1)
| O(1)
|
public func peekMin() : ?X
Return the minimal element in the heap, or null
if the heap is empty.
Example:
motoko include=initialize
heap.put("apple");
heap.put("banana");
heap.put("cantaloupe");
heap.peekMin() // => ?"apple"
| Runtime | Space |
|-----------|-----------|
| O(1)
| O(1)
|
public func deleteMin()
Delete the minimal element in the heap, if it exists.
Example:
motoko include=initialize
heap.put("apple");
heap.put("banana");
heap.put("cantaloupe");
heap.deleteMin();
heap.peekMin(); // => ?"banana"
| Runtime | Space |
|--------------|-------------|
| O(log(n))
| O(log(n))
|
public func removeMin() : (minElement : ?X)
Delete and return the minimal element in the heap, if it exists.
Example:
motoko include=initialize
heap.put("apple");
heap.put("banana");
heap.put("cantaloupe");
heap.removeMin(); // => ?"apple"
| Runtime | Space |
|--------------|-------------|
| O(log(n))
| O(log(n))
|
public 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:
motoko include=initialize
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 | Space |
|-----------|-----------|
| O(1)
| O(1)
|
public 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:
motoko include=initialize
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 | Space |
|-----------|-----------|
| O(1)
| O(1)
|
public 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:
motoko include=initialize
let entries = ["banana", "apple", "cantaloupe"];
let iter = entries.vals();
let newHeap = Heap.fromIter<Text>(iter, Text.compare);
newHeap.peekMin() // => ?"apple"
| Runtime | Space |
|-----------|-----------|
| O(size)
| O(size)
|