Struct rudac::heap::BinomialHeap

pub struct BinomialHeap<T: Ord> { /* fields omitted */ }

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

impl<T: Ord> BinomialHeap<T>

pub fn init_min(payload: T) -> BinomialHeap<T>

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");

pub fn init_max(payload: T) -> BinomialHeap<T>

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>

Merges two binomial heaps and returns the merged binomial heap

Arguments:

• binomial_heap_1: first binomial heap
• binomial_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"))

pub fn push(&mut self, payload: T)

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"))

pub fn pop(&mut self) -> Option<T>

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));

pub fn peek(&self) -> &Option<T>

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);

pub fn clear(&mut self)

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);

pub fn size(&self) -> usize

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);

pub fn is_min(&self) -> bool

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);

pub fn is_max(&self) -> bool

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);

pub fn is_empty(&self) -> bool

Returns true if there are no more items in the heap

Examples

use rudac::heap::BinomialHeap;

let mut binomial_heap = BinomialHeap::init_min(0);
assert_eq!(binomial_heap.is_empty(), false);

binomial_heap.pop();
assert_eq!(binomial_heap.is_empty(), true);

impl<T: Ord + Display> BinomialHeap<T>

pub fn preorder(binomial_heap: &BinomialHeap<T>) -> String

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");

Trait Implementations

impl<T: Debug + Ord> Debug for BinomialHeap<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.