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 264 of file fibonacci_heap.hpp.
|
private |
Definition at line 416 of file fibonacci_heap.hpp.
void clear | ( | ) |
Clears all nodes in heap
Definition at line 197 of file fibonacci_heap.hpp.
|
private |
Clears node by index
Definition at line 384 of file fibonacci_heap.hpp.
|
private |
Consolidates heap
Definition at line 295 of file fibonacci_heap.hpp.
|
private |
Cuts child node from childs list of parent
Definition at line 399 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 230 of file fibonacci_heap.hpp.
bool empty | ( | ) | const |
Definition at line 118 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 142 of file fibonacci_heap.hpp.
int get_capacity | ( | ) |
Definition at line 133 of file fibonacci_heap.hpp.
int get_key | ( | int | index, |
ScalarType & | ret_key | ||
) |
int get_num_nodes | ( | ) | const |
Definition at line 123 of file fibonacci_heap.hpp.
int get_num_trees | ( | ) |
Definition at line 128 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 97 of file fibonacci_heap.hpp.
|
private |
Links right node to childs of left node
Definition at line 351 of file fibonacci_heap.hpp.
|
private |
|
protected |
supporting array
Definition at line 452 of file fibonacci_heap.hpp.
|
protected |
size of supporting array
Definition at line 455 of file fibonacci_heap.hpp.
|
protected |
maximum number of nodes
Definition at line 449 of file fibonacci_heap.hpp.
|
protected |
minimal root in heap
Definition at line 437 of file fibonacci_heap.hpp.
|
protected |
array of nodes for fast search by index
Definition at line 440 of file fibonacci_heap.hpp.
|
protected |
number of nodes
Definition at line 443 of file fibonacci_heap.hpp.
|
protected |
number of trees
Definition at line 446 of file fibonacci_heap.hpp.