priority_queue.ex

defmodule PriorityQueue do
  @moduledoc """
  A priority queue in Elixir.
  """
  
  @type priority :: integer() | nil
  
  @type element :: any()
  
  @type t :: %__MODULE__{set: :gb_sets.set({priority(), element()})}
  
  defstruct [set: :gb_sets.empty()]

  @doc """
  Create a new priority queue.
  """
  @spec new() :: t()
  @spec new([{priority(), element()}]) :: t()
  def new(), do: %__MODULE__{set: :gb_sets.empty()}
  def new([]), do: new()
  def new([{_priority, _element} | _] = list), do: %__MODULE__{set: :gb_sets.from_list(list)}

  @doc """
  Add an element with a priority.
  """
  @specc add_with_priority(t(), element(), priority()) :: t()
  def add_with_priority(%__MODULE__{} = queue, element, priority) do
    %{queue | set: :gb_sets.add({priority, element}, queue.set)}
  end

  @doc """
  Get the size of the queue.
  """
  @spec size(t()) :: non_neg_integer()
  def size(%__MODULE__{} = queue) do
    :gb_sets.size(queue.set)
  end

  @doc """
  Extract the element with the lowest priority.
  """
  @spec extract_min(t()) :: {{priority(), element()}, t()}
  def extract_min(%__MODULE__{} = queue) do
    case :gb_sets.size(queue.set) do
      0 -> :empty
      _else ->
        {{priority, element}, set} = :gb_sets.take_smallest(queue.set)
        {{priority, element}, %{queue | set: set}}
    end
  end

  defimpl Inspect do
    import Inspect.Algebra

    def inspect(%PriorityQueue{} = queue, opts) do
      concat(["#PriorityQueue.new(", to_doc(:gb_sets.to_list(queue.set), opts), ")"])
    end
  end
end

Originally from: https://blog.ftes.de/elixir-dijkstras-algorithm-with-priority-queue-f6022d710877