orx-priority-queue

优先队列特性和高性能 d-ary 堆实现。

A. 优先队列特性和方法

该库旨在提供具有优先队列抽象的算法。为此，定义了两个特质：PriorityQueue<N, K> 和 PriorityQueueDecKey<N, K>。前者是一个简单的队列，而后者通过提供更改队列中现有项优先级的方法扩展了它。

这种分离很重要，因为额外的操作通常需要实现者分配内部内存进行记录。因此，我们仅在需要更改优先级时才更喜欢 PriorityQueueDecKey<N, K>。

有关何时需要 decrease-key 操作以及为什么它们很重要的讨论，请参阅DecreaseKey部分。

B. d-ary 堆实现

提供了三类 d-ary 堆实现。

所有堆类型都有一个常量泛型参数 D，它定义了树中每个节点的最大子节点数。请注意，d-ary 堆是二叉堆的推广，其中 d=2。

• 随着 d 的增大：每层的比较次数增加，而树的高度减小。
• 随着 d 的减小：每层所需的比较次数减少，而树变深。

没有适用于所有用例的占优变体。二叉堆通常由于其实现简单而成为首选。然而，该库中的 d-ary 实现利用了 const generics，提供了一般化，使得在不同变体之间切换变得容易。动机是允许调整堆以适应算法和相关的输入集，从而提高性能关键方法。

DaryHeap

这是实现 PriorityQueue<N, K> 的基本 d-ary 堆。除非需要优先级更新或降键操作，否则它将是默认选择。

DaryHeapOfIndices

这是一个与位置数组配对的 d-ary 堆，并实现了 PriorityQueueDecKey<N, K>。

• 它要求节点实现 HasIndex 特性，这实际上就是一个 fn index(&self) -> usize 函数。请注意，usize、u64 等，已经实现了 HasIndex。
• 此外，它还需要知道预期进入队列的最大索引（来自闭集合的候选者）。

一旦满足这些条件，它的性能将比替代的降键队列显著更快。尽管闭集合要求可能听起来很严格，但在数学算法中通常自然满足。例如，对于大多数网络遍历算法，候选者集合是图中的节点，或者是 0..num_nodes 中的索引。

在满足要求的情况下，这是默认的降键队列。

DaryHeapWithMap

这是一个与位置映射（当无 std 时为 HashMap 或 BTreeMap）配对的 d-ary 堆，并实现了 PriorityQueueDecKey<N, K>。

这是最通用的降键队列，提供了开集合的灵活性，适用于几乎所有情况。

其他队列

此外，此包还提供了以下外部数据结构的队列实现

• std::collections::BinaryHeap<(N, K)> 仅实现了 PriorityQueue<N, K>，
• priority_queue:PriorityQueue<N, K> 实现了 PriorityQueue<N, K> 和 PriorityQueueDecKey<N, K>
  • 需要 --features impl_priority_queue

这允许您无缝切换使用所有队列实现并衡量性能。

性能 & 基准测试

在测试的 "src/benches" 中的场景中

• DaryHeap 在简单的队列操作中比 std::collections::BinaryHeap 稍快；
• DaryHeapOfIndices 在需要降键操作的场景中比实现 PriorityQueueDecKey 的队列快得多。

请参阅 基准测试 部分，以了解实验和观察结果。

C. 示例

C.1. 基本用法

use orx_priority_queue::*;

// generic over simple priority queues
fn test_priority_queue<P>(mut pq: P)
where
    P: PriorityQueue<usize, f64>,
{
    pq.clear();

    pq.push(0, 42.0);
    assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&42.0), pq.peek().map(|x| x.key()));

    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);
    }
}

// generic over decrease-key priority queues
fn test_priority_queue_deckey<P>(mut pq: P)
where
    P: PriorityQueueDecKey<usize, f64>,
{
    pq.clear();

    pq.push(0, 42.0);
    assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&42.0), pq.peek().map(|x| x.key()));

    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), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&7.0), pq.peek().map(|x| x.key()));

    let deckey_result = pq.try_decrease_key(&0, 10.0);
    assert!(matches!(ResTryDecreaseKey::Unchanged, deckey_result));
    assert_eq!(Some(&0), pq.peek().map(|x| x.node()));
    assert_eq!(Some(&7.0), pq.peek().map(|x| x.key()));

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

// d-ary heap generic over const d
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_index_bound(100));

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

// or type aliases for common heaps to simplify signature
// Binary or Quarternary to fix d of d-ary
test_priority_queue(BinaryHeap::default());
test_priority_queue(BinaryHeapWithMap::default());
test_priority_queue(BinaryHeapOfIndices::with_index_bound(100));
test_priority_queue_deckey(QuarternaryHeapOfIndices::with_index_bound(100));

C.2. 在 Dijkstra 最短路径中的应用

您可能会看到以下两种实现，一种使用 PriorityQueue，另一种使用 PriorityQueueDecKey。请注意以下内容

• PriorityQueue 和 PriorityQueueDecKey 特性使算法实现支持泛型队列类型。因此，我们可以实现一个一次适用于任何队列实现的短路径算法。这允许对特定算法或输入族进行特定队列的基准测试和调整。
• 第二种实现，使用降低键队列，将大部分复杂性或账目记录推给了队列，从而导致了更简洁的算法实现。

use orx_priority_queue::*;

// Some additional types to set up the example

type Weight = u32;

pub struct Edge {
    head: usize,
    weight: Weight,
}

pub struct Graph(Vec<Vec<Edge>>);

impl Graph {
    fn num_nodes(&self) -> usize {
        self.0.len()
    }

    fn out_edges(&self, node: usize) -> impl Iterator<Item = &Edge> {
        self.0[node].iter()
    }
}

// Implementation using a PriorityQueue

fn dijkstras_with_basic_pq<Q: PriorityQueue<usize, Weight>>(
    graph: &Graph,
    queue: &mut Q,
    source: usize,
    sink: usize,
) -> Option<Weight> {
    // reset
    queue.clear();
    let mut dist = vec![Weight::MAX; graph.num_nodes()];

    // init
    dist[source] = 0;
    queue.push(source, 0);

    // iterate
    while let Some((node, cost)) = queue.pop() {
        if node == sink {
            return Some(cost);
        } else if cost > dist[node] {
            continue;
        }

        let out_edges = graph.out_edges(node);
        for Edge { head, weight } in out_edges {
            let next_cost = cost + weight;
            if next_cost < dist[*head] {
                queue.push(*head, next_cost);
                dist[*head] = next_cost;
            }
        }
    }

    None
}

// Implementation using a PriorityQueueDecKey

fn dijkstras_with_deckey_pq<Q: PriorityQueueDecKey<usize, Weight>>(
    graph: &Graph,
    queue: &mut Q,
    source: usize,
    sink: usize,
) -> Option<Weight> {
    // reset
    queue.clear();
    let mut visited = vec![false; graph.num_nodes()];

    // init
    visited[source] = true;
    queue.push(source, 0);

    // iterate
    while let Some((node, cost)) = queue.pop() {
        if node == sink {
            return Some(cost);
        }

        let out_edges = graph.out_edges(node);
        for Edge { head, weight } in out_edges {
            if !visited[*head] {
                queue.try_decrease_key_or_push(&head, cost + weight);
            }
        }
        visited[node] = true;
    }

    None
}

// TESTS: basic priority queues

let e = |head: usize, weight: Weight| Edge { head, weight };
let graph = Graph(vec![
    vec![e(1, 4), e(2, 5)],
    vec![e(0, 3), e(2, 6), e(3, 1)],
    vec![e(1, 3), e(3, 9)],
    vec![],
]);

let mut pq = BinaryHeap::new();
assert_eq!(Some(5), dijkstras_with_basic_pq(&graph, &mut pq, 0, 3));
assert_eq!(None, dijkstras_with_basic_pq(&graph, &mut pq, 3, 1));

let mut pq = QuarternaryHeap::new();
assert_eq!(Some(5), dijkstras_with_basic_pq(&graph, &mut pq, 0, 3));
assert_eq!(None, dijkstras_with_basic_pq(&graph, &mut pq, 3, 1));

let mut pq = DaryHeap::<_, _, 8>::new();
assert_eq!(Some(5), dijkstras_with_basic_pq(&graph, &mut pq, 0, 3));
assert_eq!(None, dijkstras_with_basic_pq(&graph, &mut pq, 3, 1));

// TESTS: decrease key priority queues

let mut pq = BinaryHeapOfIndices::with_index_bound(graph.num_nodes());
assert_eq!(Some(5), dijkstras_with_deckey_pq(&graph, &mut pq, 0, 3));
assert_eq!(None, dijkstras_with_deckey_pq(&graph, &mut pq, 3, 1));

let mut pq = DaryHeapOfIndices::<_, _, 8>::with_index_bound(graph.num_nodes());
assert_eq!(Some(5), dijkstras_with_deckey_pq(&graph, &mut pq, 0, 3));
assert_eq!(None, dijkstras_with_deckey_pq(&graph, &mut pq, 3, 1));

let mut pq = BinaryHeapWithMap::new();
assert_eq!(Some(5), dijkstras_with_deckey_pq(&graph, &mut pq, 0, 3));
assert_eq!(None, dijkstras_with_deckey_pq(&graph, &mut pq, 3, 1));

贡献

欢迎贡献！如果您发现错误、有问题或者认为某些东西可以改进，请打开问题或创建一个PR。

许可证

本库受MIT许可证许可。有关详细信息，请参阅LICENSE。