Struct rudac::heap::FibonacciHeap [−][src]
pub struct FibonacciHeap<T: Ord> { /* fields omitted */ }
Expand description
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
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);
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);
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>
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 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")
);
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")
);
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));
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);
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);
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);
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);
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")
);