[−][src]Struct rudac::heap::FibonacciHeap
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>
[src]
pub fn init_min() -> FibonacciHeap<T>
[src]
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>
[src]
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)
[src]
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>
[src]
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 heapfibonacci_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>
[src]
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>
[src]
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)
[src]
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
[src]
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
[src]
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
[src]
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
[src]
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,
[src]
T: Ord + Display,
pub fn preorder(fibonacci_heap: &FibonacciHeap<T>) -> String
[src]
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
Auto Trait Implementations
impl<T> RefUnwindSafe for FibonacciHeap<T> where
T: RefUnwindSafe,
T: RefUnwindSafe,
impl<T> Send for FibonacciHeap<T> where
T: Send,
T: Send,
impl<T> Sync for FibonacciHeap<T> where
T: Sync,
T: Sync,
impl<T> Unpin for FibonacciHeap<T> where
T: Unpin,
T: Unpin,
impl<T> UnwindSafe for FibonacciHeap<T> where
T: RefUnwindSafe + UnwindSafe,
T: RefUnwindSafe + UnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,