Tapkee
|
#include <fibonacci_heap.hpp>
Public Member Functions | |
fibonacci_heap (int capacity) | |
~fibonacci_heap () | |
void | insert (int index, ScalarType key) |
bool | empty () const |
int | get_num_nodes () const |
int | get_num_trees () |
int | get_capacity () |
int | extract_min (ScalarType &ret_key) |
void | clear () |
int | get_key (int index, ScalarType &ret_key) |
void | decrease_key (int index, ScalarType &key) |
Protected Attributes | |
fibonacci_heap_node * | min_root |
fibonacci_heap_node ** | nodes |
int | num_nodes |
int | num_trees |
int | max_num_nodes |
fibonacci_heap_node ** | A |
int | Dn |
Private Member Functions | |
fibonacci_heap () | |
fibonacci_heap (const fibonacci_heap &fh) | |
fibonacci_heap & | operator= (const fibonacci_heap &fh) |
void | add_to_roots (fibonacci_heap_node *up_node) |
void | consolidate () |
void | link_nodes (fibonacci_heap_node *y, fibonacci_heap_node *x) |
void | clear_node (int index) |
void | cut (fibonacci_heap_node *child, fibonacci_heap_node *parent) |
void | cascading_cut (fibonacci_heap_node *tree) |
the class fibonacci_heap, a fibonacci heap. Generally used by Isomap for Dijkstra heap algorithm
w: http://en.wikipedia.org/wiki/Fibonacci_heap
Definition at line 62 of file fibonacci_heap.hpp.
fibonacci_heap | ( | int | capacity | ) |
Constructor for heap with specified capacity
Definition at line 67 of file fibonacci_heap.hpp.
~fibonacci_heap | ( | ) |
Definition at line 84 of file fibonacci_heap.hpp.
|
private |
|
private |
|
private |
Adds node to roots list
Definition at line 265 of file fibonacci_heap.hpp.
|
private |
Definition at line 417 of file fibonacci_heap.hpp.
void clear | ( | ) |
Clears all nodes in heap
Definition at line 198 of file fibonacci_heap.hpp.
|
private |
Clears node by index
Definition at line 385 of file fibonacci_heap.hpp.
|
private |
Consolidates heap
Definition at line 296 of file fibonacci_heap.hpp.
|
private |
Cuts child node from childs list of parent
Definition at line 400 of file fibonacci_heap.hpp.
void decrease_key | ( | int | index, |
ScalarType & | key | ||
) |
Decreases key by index Have amortized time of O(1)
Definition at line 231 of file fibonacci_heap.hpp.
bool empty | ( | ) | const |
Definition at line 119 of file fibonacci_heap.hpp.
int extract_min | ( | ScalarType & | ret_key | ) |
Deletes and returns item with minimal key Have amortized time of O(log n)
Definition at line 143 of file fibonacci_heap.hpp.
int get_capacity | ( | ) |
Definition at line 134 of file fibonacci_heap.hpp.
int get_key | ( | int | index, |
ScalarType & | ret_key | ||
) |
int get_num_nodes | ( | ) | const |
Definition at line 124 of file fibonacci_heap.hpp.
int get_num_trees | ( | ) |
Definition at line 129 of file fibonacci_heap.hpp.
void insert | ( | int | index, |
ScalarType | key | ||
) |
Inserts nodes with certain key in array of nodes with index Have time of O(1)
Definition at line 98 of file fibonacci_heap.hpp.
|
private |
Links right node to childs of left node
Definition at line 352 of file fibonacci_heap.hpp.
|
private |
|
protected |
supporting array
Definition at line 453 of file fibonacci_heap.hpp.
|
protected |
size of supporting array
Definition at line 456 of file fibonacci_heap.hpp.
|
protected |
maximum number of nodes
Definition at line 450 of file fibonacci_heap.hpp.
|
protected |
minimal root in heap
Definition at line 438 of file fibonacci_heap.hpp.
|
protected |
array of nodes for fast search by index
Definition at line 441 of file fibonacci_heap.hpp.
|
protected |
number of nodes
Definition at line 444 of file fibonacci_heap.hpp.
|
protected |
number of trees
Definition at line 447 of file fibonacci_heap.hpp.