Struct rudac::heap::BinomialHeap [−][src]
pub struct BinomialHeap<T: Ord> { /* fields omitted */ }
Expand description
A binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged together
Examples
use rudac::heap::BinomialHeap;
// create a min heap
let mut binomial_heap = BinomialHeap::init_min(0);
// push items
binomial_heap.push(1);
binomial_heap.push(2);
binomial_heap.push(3);
// there are no binomial tree with rank 0
// there are no binomial tree with rank 1
// tree with rank 2 contains: 0
// | \
// 1 2
// |
// 3
assert_eq!(
BinomialHeap::preorder(&binomial_heap),
format!("Rank 0: \nRank 1: \nRank 2: 0 1 2 3\n")
);
Implementations
Initializes a min heap with the specified payload
Arguments:
payload
: data to be pushed in the heap
Examples
use rudac::heap::BinomialHeap;
let binomial_heap = BinomialHeap::init_min("rudac is awesome");
Initializes a max heap with the specified payload
Arguments:
payload
: data to be pushed in the heap
Examples
use rudac::heap::BinomialHeap;
let binomial_heap = BinomialHeap::init_max("rudac is awesome");
pub fn merge(
binomial_heap_1: BinomialHeap<T>,
binomial_heap_2: BinomialHeap<T>
) -> BinomialHeap<T>
pub fn merge(
binomial_heap_1: BinomialHeap<T>,
binomial_heap_2: BinomialHeap<T>
) -> BinomialHeap<T>
Merges two binomial heaps and returns the merged binomial heap
Arguments:
binomial_heap_1
: first binomial heapbinomial_heap_2
: second binomial heap
Panics:
- panics if two binomial heaps are not the same kind(ex. one is min heap and the other is max heap)
Examples
use rudac::heap::BinomialHeap;
let binomial_heap_1 = BinomialHeap::init_min(0);
let binomial_heap_2 = BinomialHeap::init_min(1);
let merged_heap = BinomialHeap::merge(binomial_heap_1, binomial_heap_2);
assert_eq!(BinomialHeap::preorder(&merged_heap), String::from("Rank 0: \nRank 1: 0 1\n"))
pushes specified payload
into heap
Arguments:
payload
: data to be pushed into heap
Examples
use rudac::heap::BinomialHeap;
let mut binomial_heap = BinomialHeap::init_min(0);
binomial_heap.push(1);
assert_eq!(BinomialHeap::preorder(&binomial_heap), String::from("Rank 0: \nRank 1: 0 1\n"))
Pops and returns item with highest priority. Returns None
if heap is empty
Examples
use rudac::heap::BinomialHeap;
let mut binomial_heap = BinomialHeap::init_min(0);
assert_eq!(binomial_heap.pop(), Some(0));
Returns a reference to item with highest priority
Examples
use rudac::heap::BinomialHeap;
let bh1 = BinomialHeap::init_min(0);
let bh2 = BinomialHeap::init_min(1);
let mut merged_heap = BinomialHeap::merge(bh1, bh2);
assert_eq!(*merged_heap.peek(), Some(0));
merged_heap.pop();
assert_eq!(*merged_heap.peek(), Some(1));
merged_heap.pop();
assert_eq!(*merged_heap.peek(), None);
Clears the heap and resets internal flags
Examples
use rudac::heap::BinomialHeap;
let mut binomial_heap = BinomialHeap::init_min(0);
binomial_heap.clear();
assert_eq!(binomial_heap.size(), 0);
assert_eq!(binomial_heap.pop(), None);
Returns number of items in heap
Examples
use rudac::heap::BinomialHeap;
let mut binomial_heap = BinomialHeap::init_min(0);
binomial_heap.push(1);
assert_eq!(binomial_heap.size(), 2);
Returns true if the current heap is a min heap
Examples
use rudac::heap::BinomialHeap;
let binomial_heap = BinomialHeap::init_min(0);
assert_eq!(binomial_heap.is_min(), true);
Returns true if the current heap is a max heap
Examples
use rudac::heap::BinomialHeap;
let binomial_heap = BinomialHeap::init_max(0);
assert_eq!(binomial_heap.is_max(), true);
Returns the preorder representation of the heap. it has the form of: Rank i: preorder representation of the binomial tree of rank i\n
Arguments:
binomial_heap
: reference to a binomial heap
Examples
use rudac::heap::BinomialHeap;
let mut binomial_heap = BinomialHeap::init_min(0);
binomial_heap.push(1);
binomial_heap.push(2);
binomial_heap.push(3);
binomial_heap.push(4);
binomial_heap.push(5);
binomial_heap.push(6);
assert_eq!(BinomialHeap::preorder(&binomial_heap), "Rank 0: 6\nRank 1: 4 5\nRank 2: 0 1 2 3\n");