[−][src]Crate binary_heap_plus
This crate provides BinaryHeap
which is backward-compatible with std::collections::BinaryHeap
.
Added features include:
- Heaps other than max heap.
- Optional
serde
feature.
Quick start
Max/Min Heap
For max heap, BiaryHeap::from_vec()
is the most versatile way to create a heap.
use binary_heap_plus::*; // max heap let mut h: BinaryHeap<i32> = BinaryHeap::from_vec(vec![]); // max heap with initial capacity let mut h: BinaryHeap<i32> = BinaryHeap::from_vec(Vec::with_capacity(16)); // max heap from iterator let mut h: BinaryHeap<i32> = BinaryHeap::from_vec((0..42).collect()); assert_eq!(h.pop(), Some(41));
Min heap is similar, but requires type annotation.
use binary_heap_plus::*; // min heap let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(vec![]); // min heap with initial capacity let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(Vec::with_capacity(16)); // min heap from iterator let mut h: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec((0..42).collect()); assert_eq!(h.pop(), Some(0));
Custom Heap
For custom heap, BinaryHeap::from_vec_cmp()
works in a similar way to max/min heap. The only difference is that you add the comparator closure with apropriate signature.
use binary_heap_plus::*; // custom heap: ordered by second value (_.1) of the tuples; min first let mut h = BinaryHeap::from_vec_cmp( vec![(1, 5), (3, 2), (2, 3)], |a: &(i32, i32), b: &(i32, i32)| b.1.cmp(&a.1), // comparator closure here ); assert_eq!(h.pop(), Some((3, 2)));
Constructers
Generic methods to create different kind of heaps from initial vec
data.
BinaryHeap::from_vec(vec)
BinaryHeap::from_vec_cmp(vec, cmp)
use binary_heap_plus::*; // max heap (default) let mut heap: BinaryHeap<i32> = BinaryHeap::from_vec(vec![1,5,3]); assert_eq!(heap.pop(), Some(5)); // min heap let mut heap: BinaryHeap<i32, MinComparator> = BinaryHeap::from_vec(vec![1,5,3]); assert_eq!(heap.pop(), Some(1)); // custom-sort heap let mut heap = BinaryHeap::from_vec_cmp(vec![1,5,3], |a: &i32, b: &i32| b.cmp(a)); assert_eq!(heap.pop(), Some(1)); // custom-key heap let mut heap = BinaryHeap::from_vec_cmp(vec![6,3,1], KeyComparator(|k: &i32| k % 4)); assert_eq!(heap.pop(), Some(3)); // TIP: How to reuse a comparator let mod4_comparator = KeyComparator(|k: &_| k % 4); let mut heap1 = BinaryHeap::from_vec_cmp(vec![6,3,1], mod4_comparator); assert_eq!(heap1.pop(), Some(3)); let mut heap2 = BinaryHeap::from_vec_cmp(vec![2,4,1], mod4_comparator); assert_eq!(heap2.pop(), Some(2));
Dedicated methods to create different kind of heaps
BinaryHeap::new()
creates a max heap.BinaryHeap::new_min()
creates a min heap.BinaryHeap::new_by()
creates a heap sorted by the given closure.BinaryHeap::new_by_key()
creates a heap sorted by the key generated by the given closure.
Structs
BinaryHeap | A priority queue implemented with a binary heap. |
Drain | A draining iterator over the elements of a |
FnComparator | The comparator defined by closure |
IntoIter | An owning iterator over the elements of a |
IntoIterSorted | |
Iter | An iterator over the elements of a |
KeyComparator | The comparator ordered by key |
MaxComparator | For |
MinComparator | For |
PeekMut | Structure wrapping a mutable reference to the greatest item on a
|