# `Yog.PairingHeap`
[🔗](https://github.com/code-shoily/yog_ex/blob/v0.97.0/lib/yog/pairing_heap.ex#L1)

A [Pairing Heap](https://en.wikipedia.org/wiki/Pairing_heap) implementation of a priority queue.

This module provides a priority queue with support for custom comparison functions,
making it suitable for various graph algorithms like Dijkstra's, Prim's, and A*.

Implementation inspired by [Gleamy Structures](https://github.com/schurhammer/gleamy_structures/blob/main/src/gleamy/pairing_heap.gleam)
and [ex_algo](https://github.com/code-shoily/ex_algo/blob/main/lib/ex_algo/heap/pairing_heap.ex)

## Features

- O(1) insertion
- O(1) find-min
- O(log n) amortized delete-min
- Custom comparison functions for flexible ordering
- Functional/persistent data structure

## Examples

    # Min-priority queue (default)
    pq = Yog.PairingHeap.new()
    |> Yog.PairingHeap.push(5)
    |> Yog.PairingHeap.push(3)
    |> Yog.PairingHeap.push(7)

    {:ok, 3, pq} = Yog.PairingHeap.pop(pq)

    # Max-priority queue with custom comparator
    pq = Yog.PairingHeap.new(fn a, b -> a >= b end)
    |> Yog.PairingHeap.push({:node, 5})
    |> Yog.PairingHeap.push({:node, 10})

    {:ok, {:node, 10}, _} = Yog.PairingHeap.pop(pq)

    # Priority queue for Dijkstra's algorithm
    pq = Yog.PairingHeap.new(fn {dist1, _}, {dist2, _} -> dist1 <= dist2 end)
    |> Yog.PairingHeap.push({0, :start})
    |> Yog.PairingHeap.push({5, :a})
    |> Yog.PairingHeap.push({3, :b})

## Visual Representation

<div class="graphviz">
graph G {
  bgcolor="transparent";
  node [shape=circle, fontname="inherit", color="#6366f1", fontcolor="#6366f1", penwidth=2];
  edge [color="#94a3b8", penwidth=1.5];

  node3 [label="3", color="#6366f1", penwidth=2, style=bold];
  node4 [label="4"];
  node5 [label="5"];
  node6 [label="6"];
  node7 [label="7"];

  node3 -- node5;
  node3 -- node4;
  node3 -- node6;
  node5 -- node7;
}
</div>

    iex> alias Yog.PairingHeap
    iex> pq = PairingHeap.new()
    ...> |> PairingHeap.push(3)
    ...> |> PairingHeap.push(4)
    ...> |> PairingHeap.push(5)
    ...> |> PairingHeap.push(6)
    ...> |> PairingHeap.push(7)
    iex> PairingHeap.peek(pq)
    {:ok, 3}
    iex> PairingHeap.size(pq)
    5

# `compare_fn`

```elixir
@type compare_fn() :: (any(), any() -&gt; boolean())
```

# `t`

```elixir
@type t() ::
  %Yog.PairingHeap.Node{
    children: term(),
    compare_fn: term(),
    size: term(),
    value: term()
  }
  | %Yog.PairingHeap.Empty{compare_fn: term(), size: term()}
```

# `empty?`

```elixir
@spec empty?(t()) :: boolean()
```

Checks if the priority queue is empty.

## Examples

    iex> Yog.PairingHeap.empty?(Yog.PairingHeap.new())
    true

    iex> Yog.PairingHeap.empty?(Yog.PairingHeap.new()
    ...> |> Yog.PairingHeap.push(1))
    false

# `from_list`

```elixir
@spec from_list([any()]) :: t()
```

Converts a list to a priority queue.

## Examples

    iex> pq = Yog.PairingHeap.from_list([3, 1, 4, 1, 5])
    iex> {:ok, min, _} = Yog.PairingHeap.pop(pq)
    iex> min
    1

    iex> pq = Yog.PairingHeap.from_list([3, 1, 4, 1, 5], &Kernel.>=/2)
    iex> {:ok, max, _} = Yog.PairingHeap.pop(pq)
    iex> max
    5

# `from_list`

```elixir
@spec from_list([any()], compare_fn()) :: t()
```

# `new`

```elixir
@spec new() :: t()
```

Creates a new empty priority queue.

By default, uses natural ordering (min-heap for numbers).

## Examples

    iex> pq = Yog.PairingHeap.new()
    iex> Yog.PairingHeap.empty?(pq)
    true

    iex> pq = Yog.PairingHeap.new(fn a, b -> a >= b end)  # max-heap
    iex> Yog.PairingHeap.empty?(pq)
    true

# `new`

```elixir
@spec new(compare_fn()) :: t()
```

# `peek`

```elixir
@spec peek(t()) :: {:ok, any()} | :error
```

Returns the minimum element without removing it.

Returns `{:ok, value}` if the queue is not empty, `:error` otherwise.

## Examples

    iex> pq = Yog.PairingHeap.new() |> Yog.PairingHeap.push(5) |> Yog.PairingHeap.push(3)
    iex> Yog.PairingHeap.peek(pq)
    {:ok, 3}

    iex> Yog.PairingHeap.peek(Yog.PairingHeap.new())
    :error

# `pop`

```elixir
@spec pop(t()) :: {:ok, any(), t()} | :error
```

Removes and returns the minimum element.

Returns `{:ok, value, new_queue}` if the queue is not empty, `:error` otherwise.

## Examples

    iex> pq = Yog.PairingHeap.new() |> Yog.PairingHeap.push(5) |> Yog.PairingHeap.push(3) |> Yog.PairingHeap.push(7)
    iex> {:ok, min, pq} = Yog.PairingHeap.pop(pq)
    iex> min
    3
    iex> {:ok, next_min, _} = Yog.PairingHeap.pop(pq)
    iex> next_min
    5

# `push`

```elixir
@spec push(t(), any()) :: t()
```

Inserts a value into the priority queue.

## Examples

    iex> pq =
    ...>   Yog.PairingHeap.new()
    ...>   |> Yog.PairingHeap.push(5)
    ...>   |> Yog.PairingHeap.push(3)
    iex> Yog.PairingHeap.peek(pq)
    {:ok, 3}

# `size`

```elixir
@spec size(t()) :: non_neg_integer()
```

Returns the number of elements in the queue.

## Examples

    iex> Yog.PairingHeap.new()
    ...> |> Yog.PairingHeap.push(1)
    ...> |> Yog.PairingHeap.push(2)
    ...> |> Yog.PairingHeap.size()
    2

# `to_list`

```elixir
@spec to_list(t()) :: [any()]
```

Converts the priority queue to a sorted list.

## Examples

    iex> Yog.PairingHeap.new()
    ...> |> Yog.PairingHeap.push(3)
    ...> |> Yog.PairingHeap.push(1)
    ...> |> Yog.PairingHeap.push(2)
    ...> |> Yog.PairingHeap.to_list()
    [1, 2, 3]

---

*Consult [api-reference.md](api-reference.md) for complete listing*