# PSQ [![Build Status](]([![Coverage Status](](

Priority search queues for Elixir.

## Installation

Add psq to your list of dependencies in `mix.exs`:

def deps do
  [{:psq, "~> 0.0.1"}]

## Usage

PSQ provides a purely-functional implementation of priority search queues. A
priority search queue is a data structure that efficiently supports both
associative operations (like those for `Map`) and priority-queue operations
(akin to heaps in imperative languages). The implementation is based on the
package and the associated paper.

PSQs can be created from lists in O(n log n) time. Once created, the minimum
element (`min`) and size (`Enum.count`) can be accessed in O(1) time; most
other basic operations (including `get`, `pop`, and `push`, and `delete`) are
in O(log n).

PSQs implement `Enumerable` and `Collectable`, so all your favorite functions
from `Enum` and `Stream` should work as expected.

Each entry in a PSQ has an associated *priority* and *key*. Map-like
operations, such as `get`, use keys to find the entry; all entries in a PSQ
are unique by key. Ordered operations, such as `pop` and `Enum.to_list`, use
priority to determine order (with minimum first). Priorities need not be
unique by entry; entries with the same priority will be popped in unspecified

### Examples

There are two primary ways to determine a value's priority and key in a
queue. The simplest is to start with an empty queue and input values with
priorities and keys directly, through `put/4`:

iex> q = |> PSQ.put(:a, "foo", 2) |> PSQ.put(:b, "bar", 1)
iex> q |> PSQ.get(:a)
iex> q |> PSQ.min

Alternatively, you can specify mapper functions to determine key and priority
for all entries in the queue. This is particularly useful for determining
custom priorities. For example, here's a simple method to use PSQs for

iex> q =
iex> q = [?a, ?b, ?c, ?d, ?e] |> Enum.into(q)
iex> q |> Enum.to_list
[?e, ?d, ?c, ?b, ?a]

Here's a queue that orders strings by size, using downcased strings as keys:

iex> q =, &String.downcase/1)
iex> q = ["How", "is", "your", "ocelot"] |> Enum.into(q)
iex> q |> Enum.to_list
["is", "How", "your", "ocelot"]
iex> q |> PSQ.get("how")
iex> q |> PSQ.get("How")

Priority and key mappers are also useful if you're inputting entries that are
structs or maps and want to use particular fields as keys or priorities. For

iex> q =[:priority]), &(&1[:key]))
iex> q = PSQ.put(q, %{priority: 5, key: 1})
iex> q = PSQ.put(q, %{priority: 2, key: 2})
iex> q = PSQ.put(q, %{priority: 1, key: 1})
iex> q |> PSQ.min
%{priority: 1, key: 1}
iex> q |> PSQ.get(1)
%{priority: 1, key: 1}

## Implementation

The implementation uses priority-search pennants as described in
[this paper](,
with very few modifications. Internally, tuples are used to represent nodes in
the winner/loser tree (since they offered a significant performance boost over

Testing uses the excellent [excheck]( library
for QuickCheck-style tests; benchmarking uses

## Contributing

Contributions welcome! I'd particularly welcome:

1. *Suggestions for improving the interface.* I did my best to make it
   "elixir-y", but I haven't used it enough to know if the interface makes sense
   for a variety of use-cases.

2. *Performance optimizations.* Making a queue with 10 million entries is viable
   but takes quite a long time (~120s on my machine, vs ~10s for sorting the
   equivalent list). I'd love to get the time to build a queue be roughly
   equivalent to the time to sort a list. If you want to play around with that
   stuff, be sure to use run the benchmarks before and after (`mix run