A heap Heap a takes values of type a, keeping them loosely ordered. Values can be very quickly added, and, depending on the type of heap, either the "smallest" or "biggest" value can be quickly recalled or removed.

When creating a new heap Heap a, Options a must be provided. They will determine whether the heap keeps the "smallest" or "biggest" value to hand, and how it determines how small or big the value is.

A smallest heap is a heap of any comparable type (ints, floats, chars, strings, lists, or tuples), which keeps the smallest value to hand.

>>> Heap.fromList smallest [ 0, 1, 2, 3, 4 ]
...     |> Heap.peek
Just 0

A biggest heap is a heap of any comparable type (ints, floats, chars, strings, lists, or tuples), which keeps the biggest value to hand.

>>> Heap.fromList biggest [ 0, 1, 2, 3, 4 ]
...     |> Heap.peek
Just 4

by someFunction tells the heap to sort by comparing values with the given function. This may commonly be a property of a record:

Heap.singleton (biggest |> by .yearOfBirth)
    { firstName = "Buzz"
    , lastName = "Aldrin"
    , yearOfBirth = 1930
    }

… or a hashing/consolidation function:

Heap.singleton (biggest |> by List.length)
    [ 1, 2, 3, 4, 5, 6 ]

thenBy someFunction tells the heap to use the given function to compare values, if it cannot otherwise differentiate between two values.

Heap.singleton (smallest |> by .lastName |> thenBy .firstName)
    { firstName = "Buzz"
    , lastName = "Aldrin"
    , yearOfBirth = 1930
    }

Given Heap.Options, returns an empty heap.

Heap.empty smallest
    |> Heap.push 376373


Heap.empty (smallest |> by .age)
    |> Heap.push { firstName = "Pippi", lastName = "Longstocking", age = 9 }

A heap containing one value, given Heap.Options

Heap.singleton (smallest |> by .age)
    { firstName = "Pippi", lastName = "Longstocking", age = 9 }


Heap.singleton biggest
    "Peter Piper picked a pack of pickled peppers"


Heap.singleton (biggest |> by String.length)
    "Peter Piper picked a pack of pickled peppers"

A heap containing all values in the list, given Heap.Options.

>>> Heap.fromList (biggest |> by (List.maximum >> Maybe.withDefault -999999))
...     [ [ 1, 999 ]
...     , [ 6, 4, 3, 8, 9, 347, 34, 132, 546 ]
...     ]
...         |> Heap.peek
Just [ 1, 999 ]


>>> Heap.fromList smallest []
...    |> Heap.size
0


>>> Heap.fromList smallest [ 8, 3, 8, 3, 6, 67, 23 ]
...    |> Heap.size
7

Add a value to a heap.

>>> Heap.fromList smallest [ 1, 6, 7 ]
...     |> Heap.push 4
...     |> Heap.peek
Just 1


>>> Heap.fromList smallest [ 5, 6, 7 ]
...     |> Heap.push 4
...     |> Heap.peek
Just 4

Merge the second heap into the first heap.

Note This function assumes that both heaps are sorted using the same method. Strictly speaking, the merged heap has the same sorting method as the first heap given.

>>> Heap.isEmpty (Heap.mergeInto (Heap.empty smallest) (Heap.empty smallest))
True


>>> Heap.mergeInto (Heap.fromList smallest [ 2, 4, 6, 7 ]) (Heap.fromList smallest [ 5, 7, 9, 3 ])
...     |> Heap.size
8

Try to remove the top value from the heap, returning the value and the new heap. If the heap is empty, return Nothing.

>>> Heap.pop (Heap.empty biggest)
Nothing


>>> Heap.fromList smallest [ 3, 5, 7, 7, 2, 9 ]
...     |> Heap.pop
...     |> Maybe.map (Tuple.mapSecond Heap.size)
Just (2, 5)

Try to remove the top value from the heap, returning just the new heap. If the heap is empty, return Nothing.

>>> Heap.popBlind (Heap.empty smallest)
Nothing


>>> Heap.singleton smallest 3
...     |> Heap.popBlind
...     |> Maybe.map Heap.size
Just 0

True if the Heap is empty, otherwise False.

>>> Heap.isEmpty (Heap.empty smallest)
True


>>> Heap.isEmpty (Heap.singleton smallest 3)
False

Number of elements in heap.

>>> Heap.size (Heap.empty biggest)
0


>>> Heap.size (Heap.fromList biggest [ 1, 2, 3, 4, 5, 6, 7, 8 ])
8

Look at smallest/biggest value in heap without applying any transformations.

>>> Heap.peek (Heap.empty smallest)
Nothing


>>> Heap.peek (Heap.fromList smallest [ 3, 56, 8, 367, 0, 4 ])
Just 0


>>> Heap.peek (Heap.fromList biggest [ 3, 56, 8, 367, 0, 4 ])
Just 367

Get all values from the heap, in order.

>>> Heap.toList (Heap.fromList smallest [ 9, 3, 6, 4, 1, 2, 8, 5, 7 ])
[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

Get all values from the heap, in reverse order.

>>> Heap.toListReverse (Heap.fromList smallest [ 9, 3, 6, 4, 1, 2, 8, 5, 7 ])
[ 9, 8, 7, 6, 5, 4, 3, 2, 1 ]

Get all values out as fast as possible, regardless of order