Struct rudac::heap::FibonacciHeap

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

A Fibonacci heap is a data structure for priority queue operations. It has a better amortized running time than binary heap and binomial heap.

Examples

use rudac::heap::FibonacciHeap;

// initialize a fibonacci heap
let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();

// push items into heap
fibonacci_heap.push(0);
fibonacci_heap.push(1);
fibonacci_heap.push(3);

// heap will have the shape:
//  min
//   |
//   0 <-> 1 <-> 2
assert_eq!(
    FibonacciHeap::preorder(&fibonacci_heap),
    String::from("Priority: 0\nTree 1: 1\nTree 2: 3\n")
)

Implementations

impl<T: Ord> FibonacciHeap<T>

pub fn init_min() -> FibonacciHeap<T>

Initializes a min heap with the specified payload

Examples

use rudac::heap::FibonacciHeap;

let fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();

assert_eq!(fibonacci_heap.is_min(), true);

pub fn init_max() -> FibonacciHeap<T>

Initializes a max heap with the specified payload

Examples

use rudac::heap::FibonacciHeap;

let fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_max();

assert_eq!(fibonacci_heap.is_max(), true);

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

Pushes specified payload into heap

Arguments:

• payload: data to be pushed into heap

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();

// push items into heap
fibonacci_heap.push(0);
fibonacci_heap.push(1);
fibonacci_heap.push(3);

// heap will have the shape:
//  min
//   |
//   0 <-> 1 <-> 2
assert_eq!(
    FibonacciHeap::preorder(&fibonacci_heap),
    String::from("Priority: 0\nTree 1: 1\nTree 2: 3\n")
)

pub fn merge(
    fibonacci_heap_1: FibonacciHeap<T>,
    fibonacci_heap_2: FibonacciHeap<T>
) -> FibonacciHeap<T>

Merges two fibonacci heaps and returns the merged fibonacci heap

Arguments:

• fibonacci_heap_1: first fibonacci heap
• fibonacci_heap_2: second fibonacci heap

Panics:

• panics if two fibonacci heaps are not the same kind(ex. one is min heap and the other is max heap)

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap_1: FibonacciHeap<usize> = FibonacciHeap::init_min();
fibonacci_heap_1.push(0);
fibonacci_heap_1.push(2);

let mut fibonacci_heap_2: FibonacciHeap<usize> = FibonacciHeap::init_min();
fibonacci_heap_2.push(1);
fibonacci_heap_2.push(3);

let merged_heap = FibonacciHeap::merge(fibonacci_heap_2, fibonacci_heap_1);

assert_eq!(
    FibonacciHeap::preorder(&merged_heap),
    String::from("Priority: 0\nTree 1: 3\nTree 2: 2\nTree 3: 1\n")
);

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

Pops and returns item with highest priority. Returns None if heap is empty. After pop, heap will be consolidated

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();
fibonacci_heap.push(2);
fibonacci_heap.push(3);
fibonacci_heap.push(0);
fibonacci_heap.push(1);

// before pop
assert_eq!(
    FibonacciHeap::preorder(&fibonacci_heap),
    String::from("Priority: 0\nTree 1: 3\nTree 2: 2\nTree 3: 1\n")    
);

assert_eq!(fibonacci_heap.pop(), Some(0));

// heap trees are consolidated
assert_eq!(
    FibonacciHeap::preorder(&fibonacci_heap),
    String::from("Priority: 1\nTree 1: 2 3\n")
);

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

Returns a reference to item with highest priority

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();

fibonacci_heap.push(0);

assert_eq!(*fibonacci_heap.peek(), Some(0));

pub fn clear(&mut self)

Clears the heap and resets internal flags

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();
fibonacci_heap.push(0);

fibonacci_heap.clear();

assert_eq!(fibonacci_heap.size(), 0);
assert_eq!(fibonacci_heap.pop(), None);

pub fn is_empty(&self) -> bool

Returns true if there are no more items in the heap

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();

fibonacci_heap.push(0);
assert_eq!(fibonacci_heap.is_empty(), false);

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

pub fn size(&self) -> usize

Returns number of items in heap

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();
fibonacci_heap.push(0);
fibonacci_heap.push(1);

assert_eq!(fibonacci_heap.size(), 2);

pub fn is_min(&self) -> bool

Returns true if the heap is initialized as a min heap

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();

assert_eq!(fibonacci_heap.is_min(), true);

pub fn is_max(&self) -> bool

Returns true if the heap is initialized as a max heap

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_max();

assert_eq!(fibonacci_heap.is_max(), true);

impl<T> FibonacciHeap<T> where
    T: Ord + Display, 

pub fn preorder(fibonacci_heap: &FibonacciHeap<T>) -> String

Returns the preorder representation of the heap. it has the form of:
Priority: preorder representation of tree containing priority value\n Tree i: preorder representation of the internal tree of rank i\n

Arguments:

• fibonacci_heap: reference to a fibonacci heap

Examples

use rudac::heap::FibonacciHeap;

let mut fibonacci_heap: FibonacciHeap<usize> = FibonacciHeap::init_min();
for i in 0..14 {
    fibonacci_heap.push(i)
}

fibonacci_heap.pop();

assert_eq!(
    FibonacciHeap::preorder(&fibonacci_heap),
    String::from("Priority: 1 2 3 4 5 6 7 8\nTree 1: 13\nTree 2: 9 10 11 12\n")
);

Trait Implementations

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

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

Formats the value using the given formatter.