Module priority_queue

An adaptable priority queue implementation

About

This structure adds key and priority mutation as well as entry removal operations over the base binary heap in this library. You can use the bare-bones binary heap to implement Dijkstra’s algorithm, but this adaptable priority queue implementation avoids creating duplicate key entries which reduces spatial complexity and can potentially improve temporal performance.

The primary struct PriorityQueue<K, P> provides the ability to mutate both key K and priority P after insertion while maintaining O(log(n)) (or better) operations. It is the caller’s responsibility to ensure that the keying schemes they use guarantees uniqueness to maintain the structure’s integrity. The structure inherits the underlying binary heap property in that equal priorities do not guarantee deterministic ordering, and different insertion or removal sequences on the same set of values may yield different internal heap layouts.

Design

The composite desgin of this structure provides O(log(n)) insert, remove, and key/priority mutation operations. The structure uses a Vec-based heap as its primary backing and ordering structure. In addition to the heap, this design also uses a map for (private) find(k) opertions that run in O(1) time. The map lookups allow heap mutation operaitons to avoid O(n) (n/2 average) lookups. Due to the map’s deletion logic, removed items are technically leaked which grows the map with key mutations. Key mutation operations amortize temporal complexity to O(1).

Insertion

You have the option to YOLO your way through your list by calling put(K, P) which overwrites the priorty for existing keys, or by using try_put(K, P) which returns Result if the key already exists in the queue.

Example

    use dsa_rust::composite::priority_queue::PriorityQueue;

    // Build the queue
    // NOTE: The ordering of equal priorities is NOT guaranteed
    // Postcondition: [{Bobson, 2}, {Peter, 3}, {Brain, 3}]
    let mut queue = PriorityQueue::<&str, u8>::new();
    queue.put("Peter", 3);
    queue.put("Bobson", 2);
    queue.put("Brain", 3);

    //let mut front = queue.peek().unwrap();
    let (key, priority) = queue.peek().unwrap();
    assert_eq!(key, &"Bobson");
    assert_eq!(priority, &2u8); // With type specification for clarity

    // Mutuate priority, bumping it to the front of the queue
    // Postcondition: [{Peter, 1}, {Bobson, 2}, {Brain, 3}]
    queue.mutate_priority("Peter", 1); // Mutable borrow invalidates "front"
    let (key, priority) = queue.peek().unwrap();
    assert_eq!(key, &"Peter");
    assert_eq!(priority, &1);

    // Key is already in the queue
    assert!(queue.try_put("Peter", 4).is_err());

    // Mutates the key at the front of the queue
    // Postcondition: [{Piper, 1}, {Bobson, 2}, {Brain, 3}]
    queue.mutate_key("Peter", "Piper");
    let (key, priority) = queue.peek().unwrap();
    assert_eq!(key, &"Piper");
    assert_eq!(priority, &1);

    // Pop the queue for owned values
    // Postcondition: [{Bobson, 2}, {Brain, 3}]
    let (key, priority) = queue.pop().unwrap();
    assert_eq!(key, "Piper");
    assert_eq!(priority, 1);

    // Remove a random entry
    // Postcondition: [{Brain, 3}]
    assert!(queue.contains("Bobson"));
    assert_eq!(queue.len(), 2);
    let (key, priority) = queue.remove("Bobson").unwrap();
    assert_eq!(key, "Bobson");
    assert_eq!(priority, 2);

    // Prove that its really gone
    assert!(!queue.contains("Bobson"));
    assert_eq!(queue.len(), 1);

Structs

PriorityQueue

About