Yog.PairingHeap (YogEx v0.97.0)

Copy Markdown View Source

A 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 and ex_algo

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

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; }
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

Summary

Types

compare_fn()
t()

Functions

empty?(arg1)

Checks if the priority queue is empty.

from_list(list)

Converts a list to a priority queue.

from_list(list, compare_fn)
new()

Creates a new empty priority queue.

new(compare_fn)
peek(arg1)

Returns the minimum element without removing it.

pop(arg1)

Removes and returns the minimum element.

push(heap, value)

Inserts a value into the priority queue.

size(arg1)

Returns the number of elements in the queue.

to_list(pq)

Converts the priority queue to a sorted list.

Types

compare_fn()

@type compare_fn() :: (any(), any() -> boolean())

t()

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

Functions

empty?(arg1)

@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(list)

@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(list, compare_fn)

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

new()

@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(compare_fn)

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

peek(arg1)

@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(arg1)

@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(heap, value)

@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(arg1)

@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(pq)

@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]