Crate binary_heap_plus

Expand description

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, BinaryHeap::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 BinaryHeap.
FnComparator: The comparator defined by closure
IntoIter: An owning iterator over the elements of a BinaryHeap.
IntoIterSorted
Iter: An iterator over the elements of a BinaryHeap.
KeyComparator: The comparator ordered by key
MaxComparator: For T that implements Ord, you can use this struct to quickly set up a max heap.
MinComparator: For T that implements Ord, you can use this struct to quickly set up a min heap.
PeekMut: Structure wrapping a mutable reference to the greatest item on a BinaryHeap.

Crate binary_heap_plusCopy item path