priorityqueue
A Crystal module which provides implementations for MinHeap
and MaxHeap
variants of a priority queue.
Installation
-
Add the dependency to your
shard.yml
:dependencies: priorityqueue: github: PaulSanchez/priorityqueue
-
Run
shards install
Usage
Example1
Simple scenario where the data ordering property is based on the element's values:
require "priorityqueue"
random_pq = PriorityQueue::MaxHeap(Int32).new # create a MaxHeap PriorityQueue for integers
10.times { random_pq.push rand(100) } # populate it with random numbers
until random_pq.empty? # yield the values in descending order
puts random_pq.pop
end
Example2
If priorities are distinct from their associated data, you can use Tuple
s
as in the following example (based on the Priority Queue programming task page
at rosettacode.org):
require "priorityqueue"
# Array of Tuples containing priorities and associated tasks in random order
tasks = [
{3, "Clear drains"},
{4, "Feed cat"},
{5, "Make tea"},
{1, "Solve RC tasks"},
{2, "Tax return"},
]
task_pq = PriorityQueue::MinHeap(Tuple(Int32, String)).new(tasks)
until task_pq.empty? # yield the tasks in priority order
puts task_pq.pop
end
Produces:
{1, "Solve RC tasks"}
{2, "Tax return"}
{3, "Clear drains"}
{4, "Feed cat"}
{5, "Make tea"}
Contributors
- Paul J Sanchez - creator and maintainer