Yog.PriorityQueue (YogEx v0.70.0)

A Priority Queue implementation based on Pairing Heap.

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*.

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.PriorityQueue.new()
|> Yog.PriorityQueue.push(5)
|> Yog.PriorityQueue.push(3)
|> Yog.PriorityQueue.push(7)

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

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

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

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

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.PriorityQueue.Node{children: term(), compare_fn: term(), value: term()}
  | %Yog.PriorityQueue.Empty{compare_fn: term()}

Functions

empty?(arg1)

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

Checks if the priority queue is empty.

Examples

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

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

from_list(list)

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

Converts a list to a priority queue.

Examples

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

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.PriorityQueue.new()
iex> Yog.PriorityQueue.empty?(pq)
true

iex> pq = Yog.PriorityQueue.new(fn a, b -> a >= b end)  # max-heap
iex> Yog.PriorityQueue.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.PriorityQueue.new() |> Yog.PriorityQueue.push(5) |> Yog.PriorityQueue.push(3)
iex> Yog.PriorityQueue.peek(pq)
{:ok, 3}

iex> Yog.PriorityQueue.peek(Yog.PriorityQueue.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.PriorityQueue.new() |> Yog.PriorityQueue.push(5) |> Yog.PriorityQueue.push(3) |> Yog.PriorityQueue.push(7)
iex> {:ok, min, pq} = Yog.PriorityQueue.pop(pq)
iex> min
3
iex> {:ok, next_min, _} = Yog.PriorityQueue.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.PriorityQueue.new() |> Yog.PriorityQueue.push(5) |> Yog.PriorityQueue.push(3)
iex> Yog.PriorityQueue.peek(pq)
{:ok, 3}

size(arg1)

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

Returns the number of elements in the queue.

Examples

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

to_list(pq)

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

Converts the priority queue to a sorted list.

Examples

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