libgraph v0.5.0 PriorityQueue
This module defines a priority queue datastructure, which uses a min heap structure to support pulling the values with the lowest priority out first. This is optimized for use with graph search algorithms where the smallest in/out degree or lowest edge weight/cost should be evaluated before those with higher values. Values with the same priority are dequeued in the order they were originally queued.
This implementation exploits the fact that tuple access times are extremely fast, by storing priorities as
buckets of {priority, :queue.t()}, and nesting them such that the lowest priority is always on the left,
e.g. {{1, :queue.t()}, {{3, :queue.t()}, nil}}. We use nil to mark that there have been no priorities defined
greater than the one on the left, and is where we insert new largest priorities. Inserting a new priority in the
middle is just a matter of recursively navigating the heap until we reach the tuple where the left hand is less than
the priority we’re inserting, and the right hand is greater, and creating a new nested tuple on the right.
Link to this section Summary
Functions
Create a new priority queue
Pops an element from the queue with the lowest integer value priority
Push a new element into the queue with the given priority
Link to this section Types
Link to this section Functions
Create a new priority queue
Pops an element from the queue with the lowest integer value priority.
Returns {:empty, PriorityQueue.t} if there are no elements left to dequeue.
Returns {{:value, term}, PriorityQueue.t} if the dequeue is successful
This is equivalent to the extract-min operation described in priority queue theory.
Example
iex> pq = PriorityQueue.new
...> pq = Enum.reduce(Enum.shuffle(0..4), pq, fn i, pq -> PriorityQueue.push(pq, ?a+i, i) end)
...> {{:value, ?a}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?b}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?c}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?d}, pq} = PriorityQueue.pop(pq)
...> {{:value, ?e}, pq} = PriorityQueue.pop(pq)
...> {result, _} = PriorityQueue.pop(pq)
...> result
:empty