Crate radix_heap

A monotone priority queue implemented with a radix heap.

A monotone priority queue is a variant of priority queues (itself a generalization of heaps) that requires that the extracted elements follow a monotonic sequence. This means that you cannot insert an element into a radix heap that is smaller than the last extracted element.

The key of the last extracted element is called the "top" key of the radix heap. Thus any value pushed onto the heap must be larger than or equal to the top key.

In return for this restriction, the radix heap does O(1) inserts. Popping an element is O(log m) where m is the difference between a popped key and the top key at the time the element was inserted. Note that this does not depend on the number of elements in the radix heap. This means that for workloads where this difference is bounded by a constant, the radix heap has O(1) pop.

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 using a radix heap.
Values	An iterator over values in a RadixHeapMap.

Traits

Radix

A number that can be compared using radix distance