Heap

Priority Queue

This module provides purely-functional priority queue based on leftist heap

Tree

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

Heap

class Heap<T>(ord : (T, T) -> O.Order)

share

func share() : Tree<T>

Get purely-functional representation

unsafeUnshare

func unsafeUnshare(t : Tree<T>)

Put purely-functional representation into class. Need to make sure the tree is constructed with the same compare function

put

func put(x : T)

Insert an element to the heap

peekMin

func peekMin() : ?T

Return the minimal element

deleteMin

func deleteMin()

Delete the minimal element

removeMin

func removeMin() : ?T

Remove the minimal element and return its value

fromIter

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

Convert iterator into a heap, takes O(N) time.