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 (the "top" key).

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 performance for certain algorithms like 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.top() == None);
assert!(heap.pop() == Some((9, 'c')));
assert!(heap.top() == Some(9));
assert!(heap.pop() == Some((7, 'a')));
assert!(heap.top() == Some(7));
assert!(heap.pop() == Some((2, 'b')));
assert!(heap.top() == Some(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