# Crate orx_priority_queue

Expand description

Priority queue traits, d-ary heap implementations having binary heap as a special case.

### Traits

This crate defines two priority queue traits for (node, key) pairs with the following features:

Separating more advanced `PriorityQueueDecKey` from the basic queue is due to the fact that additional functionalities are often made available through usage of additional memory.

#### Benefits of `PriorityQueueDecKey`

Decrease-key, and related operations, are critical for certain algorithms where the key of a particular node is evaluated multiple times. Without the ability to update keys of nodes on the heap, space complexity of correspoinding algorithms increases exponentially.

Consider Dijkstra’s shortest-path algorithm for instance. Space complexity of the algorithm would be O(n^2) with a `PriorityQueue` where n is the number of nodes on the graph. This is due to the fact that label of each node might be evaluated n-1 times and consequently each node can be pushed to the queue n-1 times. As also noted in `std::collections::BinaryHeap` documentation, this implementation isn’t memory-efficient as it may leave duplicate nodes in the queue.

On the other hand, using a `PriorityQueueDecKey`, space complexity of the algorithm will be kept as O(n): each node will enter the queue at most once; consequent evaluations of its label will be handled by decrease key operation.

Furthermore, the additional functionalities simplify the algorithm implementation pushing some of the complexity to the data structure. This becomes clear when the following `shortest_path` implementation is compared to the corresponding `std::collections::BinaryHeap` example. Note that it is almost a direct substitution while providing a better space complexity, generic dary-heap options and a cleaner algorithm implementation.

##### `PriorityQueue` version of Dijkstra’s shortest path algorithm

Below is the main iteration of Dijkstra’s shortest path algorithm with a basic priority queue without a decrease key operation; taken and slightly adjusted from `std::collections::BinaryHeap`.

``````// Examine the frontier with lower cost nodes first (min-heap)
while let Some((position, cost)) = heap.pop() {
// Alternatively we could have continued to find all shortest paths
if position == goal {
return Some(cost);
}

// Important as we may have already found a better way
if cost > dist[position] { continue; }

// For each node we can reach, see if we can find a way with
// a lower cost going through this node
let next = State { cost: cost + edge.cost, position: edge.node };

// If so, add it to the frontier and continue
if next.cost < dist[next.position] {
heap.push(next);
// Relaxation, we have now found a better way
dist[next.position] = next.cost;
}
}
}``````

In addition to the heap, we need to keep the `dist` array. This has two main purposes:

• to avoid visiting the same node multiple times by the check `cost > dist[position]`;
• so that we do not push non-improving labels to the queue to reduce heap pushes by `next.cost < dist[next.position]`; however, it still requires O(n^2) space complexity.

Notice that none of these would be necessary if each node entered the heap at most once and its key was updated throughout the search whenever a shorter path is found.

##### `PriorityQueueDecKey` version of Dijkstra’s shortest path algorithm

See below the `PriorityQueueDecKey` version which reduces space complexity to O(n).

The heap is now internally paired up with a positions array (`DaryHeapOfIndices`) or hash map (`DaryHeapWithMap`) with space complexity of O(n). This is already compensated by not requiring the `dist` vector.

Furthermore, it allows to simplify the algorithm implementation by pushing the main complexity to the data structure; the algorithm now simply expresses the traversal and the update.

``````// Examine the frontier with lower cost nodes first (min-heap)
while let Some((position, cost)) = heap.pop() {
// Alternatively we could have continued to find all shortest paths
if position == goal {
return Some(cost);
}

// For each node we can reach, see if we can find a way with
// a lower cost going through this node
heap.try_decrease_key_or_push(&edge.node, &(cost + edge.cost));
}
}``````

Note that `try_decrease_key_or_push` performs the following:

• if the node already exists in the queue:
• when the new `key` is strictly less than the `node`’s current key; it decreases the key of the node to the given new `key`, and returns true (a new shorter path is found, an indicator to udpate predecessor if shortest path is a required output in addition to shortest distance);
• otherwise, does not change the queue and returns false;
• otherwise, pushes the `node` with the given `key` to the queue, and returns false.

This is exactly what we need for Dijsktra’s shortest path algorithm, and many node labelling algorithms. See `PriorityQueueDecKey` for other metods of the trait.

See below, or tests/dijkstra.rs, for the complete implementation of the Dijkstra’s shortest path algorithm with a `PriorityQueueDecKey`, adjusted from the standard BinaryHeap example.

``````use orx_priority_queue::*;

// Each node is represented as a `usize`, for a shorter implementation.
struct Edge {
node: usize,
cost: usize,
}

// Dijkstra's shortest path algorithm.

// Start at `start` and use `dist` to track the current shortest distance
// to each node. This implementation isn't memory-efficient as it may leave duplicate
// nodes in the queue. It also uses `usize::MAX` as a sentinel value,
// for a simpler implementation.
fn shortest_path(adj_list: &Vec<Vec<Edge>>, start: usize, goal: usize) -> Option<usize> {
let mut heap = BinaryHeapWithMap::default();

// We're at `start`, with a zero cost
heap.push(start, 0);

// Examine the frontier with lower cost nodes first (min-heap)
while let Some((position, cost)) = heap.pop() {
// Alternatively we could have continued to find all shortest paths
if position == goal {
return Some(cost);
}

// For each node we can reach, see if we can find a way with
// a lower cost going through this node
heap.try_decrease_key_or_push(&edge.node, &(cost + edge.cost));
}
}

// Goal not reachable
None
}

// This is the directed graph we're going to use.
// The node numbers correspond to the different states,
// and the edge weights symbolize the cost of moving
// from one node to another.
// Note that the edges are one-way.
//
//                  7
//          +-----------------+
//          |                 |
//          v   1        2    |  2
//          0 -----> 1 -----> 3 ---> 4
//          |        ^        ^      ^
//          |        | 1      |      |
//          |        |        | 3    | 1
//          +------> 2 -------+      |
//           10      |               |
//                   +---------------+
//
// The graph is represented as an adjacency list where each index,
// corresponding to a node value, has a list of outgoing edges.
// Chosen for its efficiency.
let graph = vec![
// Node 0
vec![Edge { node: 2, cost: 10 }, Edge { node: 1, cost: 1 }],
// Node 1
vec![Edge { node: 3, cost: 2 }],
// Node 2
vec![
Edge { node: 1, cost: 1 },
Edge { node: 3, cost: 3 },
Edge { node: 4, cost: 1 },
],
// Node 3
vec![Edge { node: 0, cost: 7 }, Edge { node: 4, cost: 2 }],
// Node 4
vec![],
];

assert_eq!(shortest_path(&graph, 0, 1), Some(1));
assert_eq!(shortest_path(&graph, 0, 3), Some(3));
assert_eq!(shortest_path(&graph, 3, 0), Some(7));
assert_eq!(shortest_path(&graph, 0, 4), Some(5));
assert_eq!(shortest_path(&graph, 4, 0), None);``````

### Implementations

#### d-ary heap

The core d-ary heap is implemented thanks to const generics. Three structs are created from this core struct:

• `DaryHeap<N, K, const D: usize>` which implements `PriorityQueue<N, K>` to be preferred when the additional features are not required.
• `DaryHeapWithMap<N, K, const D: usize>` where `N: Hash + Equal` implements `PriorityQueueDecKey<N, K>`. It is a combination of the d-ary heap and a hash-map to track positions of nodes. This might be considered as the default way to extend the heap to enable additional funcitonalities without requiring a linear search.
• `DaryHeapOfIndices<N, K, const D: usize>` where `N: HasIndex` implements `PriorityQueueDecKey<N, K>`. This variant is and alternative to the hash-map implementation and is particularly useful in algorithms where nodes to be enqueued are sampled from a closed set with known elements and the size of the queue is likely to get close to total number of candidates.

#### Special traversal for d=2: binary-heap

const generics further allows to use special arithmetics for the special case where d=2; i.e., when d-ary heap is the binary heap. In particular, one addition/subtraction is avoided during the traversal through the tree.

However, overall performance of the queues depends on the use case, ratio of push an decrease-key operations, etc. Benchmarks will follow.

### Example

``````use orx_priority_queue::*;

fn test_priority_queue<P>(mut pq: P)
where
P: PriorityQueue<usize, f64>,
{
println!("\ntest_priority_queue");
pq.clear();

pq.push(0, 42.0);
assert_eq!(Some(&(0, 42.0)), pq.peek());

let popped = pq.pop();
assert_eq!(Some((0, 42.0)), popped);
assert!(pq.is_empty());

pq.push(0, 42.0);
pq.push(1, 7.0);
pq.push(2, 24.0);
pq.push(10, 3.0);

while let Some(popped) = pq.pop() {
println!("pop {:?}", popped);
}
}
fn test_priority_queue_deckey<P>(mut pq: P)
where
P: PriorityQueueDecKey<usize, f64>,
{
println!("\ntest_priority_queue_deckey");
pq.clear();

pq.push(0, 42.0);
assert_eq!(Some(&(0, 42.0)), pq.peek());

let popped = pq.pop();
assert_eq!(Some((0, 42.0)), popped);
assert!(pq.is_empty());

pq.push(0, 42.0);
assert!(pq.contains(&0));

pq.decrease_key(&0, &7.0);
assert_eq!(Some(&(0, 7.0)), pq.peek());

let is_key_decreased = pq.try_decrease_key(&0, &10.0);
assert!(!is_key_decreased);
assert_eq!(Some(&(0, 7.0)), pq.peek());

while let Some(popped) = pq.pop() {
println!("pop {:?}", popped);
}
}

// d of the d-ary heap
const D: usize = 4;

test_priority_queue(DaryHeap::<usize, f64, D>::default());
test_priority_queue(DaryHeapWithMap::<usize, f64, D>::default());
test_priority_queue(DaryHeapOfIndices::<usize, f64, D>::with_upper_limit(100));

test_priority_queue_deckey(DaryHeapWithMap::<usize, f64, D>::default());
test_priority_queue_deckey(DaryHeapOfIndices::<usize, f64, D>::with_upper_limit(100));``````

## Structs

• A d-ary heap which implements `PriorityQueue`, but not `PriorityQueueDecKey`.
• A d-ary heap which implements both `PriorityQueue` and `PriorityQueueDecKey`.
• A d-ary heap which implements both `PriorityQueue` and `PriorityQueueDecKey`.

## Traits

• A struct which provides an index of type usize. Index of the struct can be considered its unchanging id defined its position in a collection.
• A priority queue which allows pushing (N, K)=(node, key) pairs to the collection, and popping the foremost element having the lowest key.
• A PriorityQueueDecKey is a more advanced PriorityQueue with additional features mainly related to accessing or modifying already pushed nodes such as: