Crate radix_heap

A monotone priority queue implemented with a radix heap.

A monotone priority queue is a priority queue that only allows keys to be inserted if their priority is less than or equal to that of the last extracted key.

In this implementation, the last extracted value is known as the "top" value. The top value does not necessarily have to be the last extracted key. It can be lower, or initially it can be any value. Note that the constraint above still applies in such a case.

Insertion is O(1) time complexity, while popping is amortized O(log n). More precisely, popping is O(d) where d is the radix distance from the key to the top value at the time of insertion. This can give better asymptotic running times for certain algorithms like for example Djikstra's algorithm.

Example

extern crate radix_heap;

let mut heap = radix_heap::RadixHeapMap::new();
heap.push(7, 'a');
heap.push(2, 'b');
heap.push(9, 'c');
 
assert!(heap.pop() == Some((9, 'c')));
assert!(heap.top() == 9);
assert!(heap.pop() == Some((7, 'a')));
assert!(heap.top() == 7);
assert!(heap.pop() == Some((2, 'b')));
assert!(heap.top() == 2);
assert!(heap.pop() == None);

Structs

RadixHeapMap

A montone priority queue implemented with a radix heap.

Traits

Radix

A number that can be compared using radix distance