Packages
inplace
0.1.2
0.7.12
0.7.11
0.7.10
0.7.9
0.7.8
0.7.7
0.7.6
0.7.5
0.7.4
0.7.3
0.7.2
0.7.1
0.7.0
0.6.8
0.6.7
0.6.6
0.6.5
0.6.4
0.6.3
0.6.2
0.6.1
0.6.0
0.5.4
0.5.3
0.5.2
0.5.1
0.5.0
0.4.4
0.4.3
0.4.2
0.4.1
0.4.0
0.3.3
0.3.2
0.3.1
0.3.0
0.2.3
0.2.2
0.2.1
0.2.0
0.1.9
0.1.8
0.1.7
0.1.6
0.1.5
0.1.4
0.1.3
0.1.2
0.1.1
0.1.0
Mutable data structures
Current section
Files
Jump to
Current section
Files
test/algorithms/priority_queue_test.exs
defmodule InPlace.PriorityQueueTest do
use ExUnit.Case
alias InPlace.PriorityQueue
describe "Priority Queue" do
test "operations" do
## Create
q = PriorityQueue.new(100)
assert PriorityQueue.empty?(q)
assert PriorityQueue.size(q) == 0
refute PriorityQueue.get_min(q)
refute PriorityQueue.extract_min(q)
## Insert
PriorityQueue.insert(q, :a, 2.5)
assert PriorityQueue.size(q) == 1
refute PriorityQueue.empty?(q)
assert {:a, 2.5} == PriorityQueue.get_min(q)
PriorityQueue.insert(q, "b", 2.7)
assert {:a, 2.5} == PriorityQueue.get_min(q)
PriorityQueue.insert(q, "b", 0)
assert {"b", 0} == PriorityQueue.get_min(q)
## Extract min
assert {"b", 0} == PriorityQueue.extract_min(q)
assert {:a, 2.5} = PriorityQueue.extract_min(q)
assert {"b", 2.7} == PriorityQueue.extract_min(q)
assert PriorityQueue.empty?(q)
## The "backup" mapping
end
test "sorting, heapsort-style" do
priorities =
Enum.zip(
["abc", "def", :a, :c, {:d, 1}, {:f, 2.5}, 2, 4, 0.25, -12.99],
[ 2, 74.2, 1, 8, 22.5, -3.7, -0.5, 3.9, 5.1, 120])
|> Enum.shuffle()
q = PriorityQueue.new(length(priorities))
Enum.each(priorities, fn {key, priority} -> PriorityQueue.insert(q, key, priority) end)
desc_sorted = Enum.reduce(1..length(priorities), [],
fn _, acc -> [PriorityQueue.extract_min(q) | acc] end
)
assert Enum.sort_by(priorities, fn {_key, priority} -> priority end, :desc) == desc_sorted
end
end
end