bheap

defmodule BHeap do
  @moduledoc """
  Binomial heaps in Elixir.

  For general information about them, see [Wikipedia](https://en.wikipedia.org/wiki/Binomial_heap).

  The collection of binomial trees satisfies the following conditions:

  * Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent
  * There can only be either one or zero binomial trees for each order, including zero order
  """

  alias BHeap.BTree

  @empty []

  @doc """
  Creates a new heap.

  ## Example
      iex> BHeap.new()
      []
  """
  def new, do: @empty

  @doc """
  Creates a new heap from a given enumerable.

  ## Example
      iex> BHeap.new([1, 2])
      [{1, 1, [{0, 2, []}]}]
  """
  def new(enumerable) do
    enumerable
    |> Enum.reduce(@empty, &(put(&2,&1)))
  end

  @doc """
  Puts a new value in a heap.

  ## Example
      iex> BHeap.new() |> BHeap.put(1) |> BHeap.put(2)
      [{1, 1, [{0, 2, []}]}]
  """
  def put(bheap, value) do
    bheap
    |> put_tree_in_list(BTree.new(value))
  end

  @doc """
  Sorts the given heap and returns a list.

  ## Example
      iex> heap1 = BHeap.new([2, 4, 6, 8, 10])
      iex> heap2 = BHeap.new([1, 3, 5, 7, 9])
      iex> BHeap.merge(heap1, heap2) |> BHeap.sort()
      [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  """
  def sort(heap), do: sort(heap, [])
  defp sort(@empty, mins), do: Enum.reverse(mins)
  defp sort(heap, mins) do
    heap
    |> remove_min()
    |> sort([min(heap) | mins])
  end

  @doc """
  Returns the minimum element of a heap.

  ## Example
      iex> BHeap.new([10, 1, 7]) |> BHeap.min()
      1
  """
  def min(bheap) do
    bheap
    |> Enum.map(fn({_, value, _}) -> value end)
    |> Enum.min()
  end

  @doc """
  Removes the minimum element from a heap.

  ## Example
      iex> BHeap.new([10, 1, 7]) |> BHeap.remove_min()
      [{1, 7, [{0, 10, []}]}]
  """
  def remove_min(bheap) do
    {{_, _, rest}, rest_heaps} = remove_min_tree(bheap)

    rest
    |> Enum.reverse()
    |> merge(rest_heaps)
  end

  defp remove_min_tree([tree]), do: {tree, []}
  defp remove_min_tree([{_, value, _} = tree | rest]) do
    {{_, inner_val, _} = inner_tree, inner_rest} = remove_min_tree(rest)

    if value < inner_val do
      {tree, rest}
    else
      {inner_tree, [tree | inner_rest]}
    end
  end

  @doc """
  Merges two heaps.

  ## Example
      iex> heap1 = BHeap.new([2, 4, 6])
      iex> heap2 = BHeap.new([1, 3, 5])
      iex> BHeap.merge(heap1, heap2)
      [{1, 5, [{0, 6, []}]}, {2, 1, [{1, 2, [{0, 4, []}]}, {0, 3, []}]}]
  """
  def merge(bheap, @empty), do: bheap
  def merge(@empty, bheap), do: bheap
  def merge([tree1 | rest1] = bheap1, [tree2 | rest2] = bheap2) do
    cond do
      BTree.rank(tree1) < BTree.rank(tree2) ->
        [tree1 | merge(rest1, bheap2)]
      BTree.rank(tree1) > BTree.rank(tree2) ->
        [tree2 | merge(bheap1, rest2)]
      true ->
        put_tree_in_list(merge(rest1, rest2), BTree.link(tree1, tree2))
    end
  end

  defp put_tree_in_list([], tree), do: [tree]
  defp put_tree_in_list([first | rest] = all, tree) do
    if BTree.rank(tree) < BTree.rank(first) do
      [tree | all]
    else
      put_tree_in_list(rest, BTree.link(tree, first))
    end
  end
end