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

IntoIter	An owning iterator over key-value pairs in a RadixHeapMap.
Iter	An iterator over key-value pairs in a RadixHeapMap.
Keys	An iterator over keys in a RadixHeapMap.
RadixHeapMap	A montone priority queue implemented with a radix heap.
Values	An iterator over values in a RadixHeapMap.

Traits

Radix

A number that can be compared using radix distance