Heap (heap v3.0.0)
A heap is a special tree data structure. Good for sorting and other magic.
See also: Heap (data structure) on Wikipedia.
Link to this section Summary
Functions
Return the comparator heap is using for insert comparisons.
Test if heap is empty.
Test if the heap contains the element value.
Create an empty heap with a specific comparator.
Pop the root element off heap and discard it.
Push a new value into heap.
Return the element at the root of heap.
Return the number of elements in heap.
Return the root element and the rest of the heap in one operation.
Link to this section Types
@type t() :: %Heap{ comparator: :> | :< | (any(), any() -> boolean()), data: tuple() | nil, size: non_neg_integer() }
Link to this section Functions
comparator(heap)
@spec comparator(t()) :: :< | :>
Return the comparator heap is using for insert comparisons.
examples
Examples
iex> Heap.new(:<)
...> |> Heap.comparator()
:<empty?(heap)
Test if heap is empty.
examples
Examples
iex> Heap.new()
...> |> Heap.empty?()
true
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new())
...> |> Heap.empty?()
falsemax()
@spec max() :: t()
Create an empty max Heap.
A max heap is a heap tree which always has the largest value at the root.
examples
Examples
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.max())
...> |> Heap.root()
10member?(heap, value)
Test if the heap contains the element value.
examples
Examples
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new())
...> |> Heap.member?(11)
false
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new())
...> |> Heap.member?(7)
truemin()
@spec min() :: t()
Create an empty min Heap.
A min heap is a heap tree which always has the smallest value at the root.
examples
Examples
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.min())
...> |> Heap.root()
1new()
@spec new() :: t()
Create an empty Heap with the default comparator (<).
Defaults to >.
examples
Examples
iex> Heap.new()
...> |> Heap.comparator()
:<new(fun)
Create an empty heap with a specific comparator.
Provide a comparator option, which can be :<, :> to indicate
that the Heap should use Elixir's normal < or > comparison functions
or a custom comparator function.
## Examples
iex> Heap.new(:<)
...> |> Heap.comparator()
:<If given a function it should compare two arguments, and return true if
the first argument precedes the second one.
## Examples
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new(&(&1 > &2)))
...> |> Enum.to_list()
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
iex> Heap.new(&(Date.compare(elem(&1, 0), elem(&2, 0)) == :gt))
...> |> Heap.push({~D[2017-11-20], :jam})
...> |> Heap.push({~D[2017-11-21], :milk})
...> |> Heap.push({~D[2017-10-21], :bread})
...> |> Heap.push({~D[2017-10-20], :eggs})
...> |> Enum.map(fn {_, what} -> what end)
[:milk, :jam, :bread, :eggs]pop(heap)
Pop the root element off heap and discard it.
examples
Examples
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new())
...> |> Heap.pop()
...> |> Heap.root()
2push(heap, value)
Push a new value into heap.
examples
Examples
iex> Heap.new()
...> |> Heap.push(13)
...> |> Heap.root()
13root(heap)
Return the element at the root of heap.
examples
Examples
iex> Heap.new()
...> |> Heap.root()
nil
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new())
...> |> Heap.root()
1size(heap)
@spec size(t()) :: non_neg_integer()
Return the number of elements in heap.
examples
Examples
iex> 1..10
...> |> Enum.shuffle()
...> |> Enum.into(Heap.new())
...> |> Heap.size()
10split(heap)
Return the root element and the rest of the heap in one operation.
examples
Examples
iex> heap = 1..10 |> Enum.into(Heap.min())
...> rest = Heap.pop(heap)
...> {1, rest} == Heap.split(heap)
true