Struct priority_queue::double_priority_queue::DoublePriorityQueue [−][src]
pub struct DoublePriorityQueue<I, P, H = RandomState> where
I: Hash + Eq,
P: Ord, { /* fields omitted */ }
Expand description
A double priority queue with efficient change function to change the priority of an element.
The priority is of type P, that must implement std::cmp::Ord
.
The item is of type I, that must implement Hash
and Eq
.
Implemented as a heap of indexes, stores the items inside an IndexMap
to be able to retrieve them quickly.
With this data structure it is possible to efficiently extract both the maximum and minimum elements arbitrarily.
If your need is to always extract the minimum, use a
PriorityQueue<I, Reverse<P>>
wrapping
your priorities in the standard wrapper
Reverse<T>
.
Example
use priority_queue::DoublePriorityQueue;
let mut pq = DoublePriorityQueue::new();
assert!(pq.is_empty());
pq.push("Apples", 5);
pq.push("Bananas", 8);
pq.push("Strawberries", 23);
assert_eq!(pq.peek_max(), Some((&"Strawberries", &23)));
assert_eq!(pq.peek_min(), Some((&"Apples", &5)));
pq.change_priority("Bananas", 25);
assert_eq!(pq.peek_max(), Some((&"Bananas", &25)));
for (item, _) in pq.into_sorted_iter() {
println!("{}", item);
}
Implementations
Creates an empty DoublePriorityQueue
with the specified capacity.
impl<I, P, H> DoublePriorityQueue<I, P, H> where
P: Ord,
I: Hash + Eq,
H: BuildHasher + Default,
impl<I, P, H> DoublePriorityQueue<I, P, H> where
P: Ord,
I: Hash + Eq,
H: BuildHasher + Default,
Creates an empty DoublePriorityQueue
with the default hasher
Creates an empty DoublePriorityQueue
with the specified capacity and default hasher
Creates an empty DoublePriorityQueue
with the specified hasher
Creates an empty DoublePriorityQueue
with the specified capacity and hasher
The internal collections will be able to hold at least capacity
elements without reallocating.
If capacity
is 0, there will be no allocation.
Return an iterator in arbitrary order over the (item, priority) elements in the queue.
The item and the priority are mutable references, but it’s a logic error
to modify the item in a way that change the result of Hash
or Eq
.
It’s not an error, instead, to modify the priorities, because the heap
will be rebuilt once the IterMut
goes out of scope. It would be
rebuilt even if no priority value would have been modified, but the
procedure will not move anything, but just compare the priorities.
Returns the couple (item, priority) with the lowest priority in the queue, or None if it is empty.
Computes in O(1) time
Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.
Computes in O(1) time
Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.
The item is a mutable reference, but it’s a logic error to modify it
in a way that change the result of Hash
or Eq
.
The priority cannot be modified with a call to this function.
To modify the priority use push
, change_priority
or
change_priority_by
.
Computes in O(1) time
Returns the couple (item, priority) with the greatest priority in the queue, or None if it is empty.
The item is a mutable reference, but it’s a logic error to modify it
in a way that change the result of Hash
or Eq
.
The priority cannot be modified with a call to this function.
To modify the priority use push
, change_priority
or
change_priority_by
.
Computes in O(1) time
Returns the number of elements the internal map can hold without reallocating.
This number is a lower bound; the map might be able to hold more, but is guaranteed to be able to hold at least this many.
Shrinks the capacity of the internal data structures that support this operation as much as possible.
Removes the item with the lowest priority from the priority queue and returns the pair (item, priority), or None if the queue is empty.
Removes the item with the greatest priority from the priority queue and returns the pair (item, priority), or None if the queue is empty.
Implements a HeapSort.
Consumes the PriorityQueue and returns a vector with all the items sorted from the one associated to the lowest priority to the highest.
Implements a HeapSort
Consumes the PriorityQueue and returns a vector with all the items sorted from the one associated to the highest priority to the lowest.
pub fn into_sorted_iter(self) -> IntoSortedIter<I, P, H>ⓘNotable traits for IntoSortedIter<I, P, H>impl<I, P, H> Iterator for IntoSortedIter<I, P, H> where
I: Hash + Eq,
P: Ord, type Item = (I, P);
pub fn into_sorted_iter(self) -> IntoSortedIter<I, P, H>ⓘNotable traits for IntoSortedIter<I, P, H>impl<I, P, H> Iterator for IntoSortedIter<I, P, H> where
I: Hash + Eq,
P: Ord, type Item = (I, P);
impl<I, P, H> Iterator for IntoSortedIter<I, P, H> where
I: Hash + Eq,
P: Ord, type Item = (I, P);
Generates a new double ended iterator from self that will extract the elements from the one with the lowest priority to the highest one.
Reserves capacity for at least additional
more elements to be inserted
in the given DoublePriorityQueue
. The collection may reserve more space to avoid
frequent reallocations. After calling reserve
, capacity will be
greater than or equal to self.len() + additional
. Does nothing if
capacity is already sufficient.
Panics
Panics if the new capacity overflows usize
.
Insert the item-priority pair into the queue.
If an element equal to item
was already into the queue,
it is updated and the old value of its priority is returned in Some
;
otherwise, returns None
.
Computes in O(log(N)) time.
Increase the priority of an existing item in the queue, or insert it if not present.
If an element equal to item
is already in the queue with a
lower priority, its priority is increased to the new one
without replacing the element and the old priority is returned.
Otherwise, the new element is inserted into the queue.
Returns Some
if an element equal to item
is already in the
queue. If its priority is higher then priority
, the latter is returned back,
otherwise, the old priority is contained in the Option.
If the item is not in the queue, None
is returned.
Computes in O(log(N)) time.
Decrease the priority of an existing item in the queue, or insert it if not present.
If an element equal to item
is already in the queue with a
higher priority, its priority is decreased to the new one
without replacing the element and the old priority is returned.
Otherwise, the new element is inserted into the queue.
Returns Some
if an element equal to item
is already in the
queue. If its priority is lower then priority
, the latter is returned back,
otherwise, the old priority is contained in the Option.
If the item is not in the queue, None
is returned.
Computes in O(log(N)) time.
Change the priority of an Item returning the old value of priority,
or None
if the item wasn’t in the queue.
The argument item
is only used for lookup, and is not used to overwrite the item’s data
in the priority queue.
The item is found in O(1) thanks to the hash table. The operation is performed in O(log(N)) time.
Change the priority of an Item using the provided function. The item is found in O(1) thanks to the hash table. The operation is performed in O(log(N)) time (worst case).
Get the priority of an item, or None
, if the item is not in the queue
Get the couple (item, priority) of an arbitrary element, as reference
or None
if the item is not in the queue.
Get the couple (item, priority) of an arbitrary element, or None
if the item was not in the queue.
The item is a mutable reference, but it’s a logic error to modify it
in a way that change the result of Hash
or Eq
.
The priority cannot be modified with a call to this function.
To modify the priority use push
, change_priority
or
change_priority_by
.
Remove an arbitrary element from the priority queue. Returns the (item, priority) couple or None if the item is not found in the queue.
The operation is performed in O(log(N)) time (worst case).
Move all items of the other
queue to self
ignoring the items Eq to elements already in self
At the end, other
will be empty.
Note that at the end, the priority of the duplicated elements inside self may be the one of the elements in other, if other is longer than self
Trait Implementations
impl<I, P, H> Default for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher + Default,
impl<I, P, H> Default for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher + Default,
impl<I, P, H> Extend<(I, P)> for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<I, P, H> Extend<(I, P)> for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
Extends a collection with the contents of an iterator. Read more
extend_one
)Extends a collection with exactly one element.
extend_one
)Reserves capacity in a collection for the given number of additional elements. Read more
impl<I, P, H> From<DoublePriorityQueue<I, P, H>> for PriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<I, P, H> From<DoublePriorityQueue<I, P, H>> for PriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
Performs the conversion.
impl<I, P, H> From<PriorityQueue<I, P, H>> for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<I, P, H> From<PriorityQueue<I, P, H>> for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
Performs the conversion.
impl<I, P, H> FromIterator<(I, P)> for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher + Default,
impl<I, P, H> FromIterator<(I, P)> for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher + Default,
impl<I, P, H> IntoIterator for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<I, P, H> IntoIterator for DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<'a, I, P, H> IntoIterator for &'a DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<'a, I, P, H> IntoIterator for &'a DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
H: BuildHasher,
impl<'a, I, P, H> IntoIterator for &'a mut DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
impl<'a, I, P, H> IntoIterator for &'a mut DoublePriorityQueue<I, P, H> where
I: Hash + Eq,
P: Ord,
impl<I, P1, H1, P2, H2> PartialEq<DoublePriorityQueue<I, P2, H2>> for DoublePriorityQueue<I, P1, H1> where
I: Hash + Eq,
P1: Ord,
P1: PartialEq<P2>,
Option<P1>: PartialEq<Option<P2>>,
P2: Ord,
H1: BuildHasher,
H2: BuildHasher,
impl<I, P1, H1, P2, H2> PartialEq<DoublePriorityQueue<I, P2, H2>> for DoublePriorityQueue<I, P1, H1> where
I: Hash + Eq,
P1: Ord,
P1: PartialEq<P2>,
Option<P1>: PartialEq<Option<P2>>,
P2: Ord,
H1: BuildHasher,
H2: BuildHasher,
Auto Trait Implementations
impl<I, P, H> RefUnwindSafe for DoublePriorityQueue<I, P, H> where
H: RefUnwindSafe,
I: RefUnwindSafe,
P: RefUnwindSafe,
impl<I, P, H> Send for DoublePriorityQueue<I, P, H> where
H: Send,
I: Send,
P: Send,
impl<I, P, H> Sync for DoublePriorityQueue<I, P, H> where
H: Sync,
I: Sync,
P: Sync,
impl<I, P, H> Unpin for DoublePriorityQueue<I, P, H> where
H: Unpin,
I: Unpin,
P: Unpin,
impl<I, P, H> UnwindSafe for DoublePriorityQueue<I, P, H> where
H: UnwindSafe,
I: UnwindSafe,
P: UnwindSafe,
Blanket Implementations
Mutably borrows from an owned value. Read more
Compare self to key
and return true
if they are equal.