Tapkee
fibonacci_heap Class Reference

#include <fibonacci_heap.hpp>

List of all members.

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_nodemin_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_heapoperator= (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)

Detailed Description

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.


Constructor & Destructor Documentation

fibonacci_heap ( int  capacity)

Constructor for heap with specified capacity

Definition at line 67 of file fibonacci_heap.hpp.

Definition at line 84 of file fibonacci_heap.hpp.

fibonacci_heap ( ) [private]
fibonacci_heap ( const fibonacci_heap fh) [private]

Member Function Documentation

void add_to_roots ( fibonacci_heap_node up_node) [private]

Adds node to roots list

Definition at line 265 of file fibonacci_heap.hpp.

void cascading_cut ( fibonacci_heap_node tree) [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.

void clear_node ( int  index) [private]

Clears node by index

Definition at line 385 of file fibonacci_heap.hpp.

void consolidate ( ) [private]

Consolidates heap

Definition at line 296 of file fibonacci_heap.hpp.

void cut ( fibonacci_heap_node child,
fibonacci_heap_node parent 
) [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)

Returns:
item with minimal key

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 
)

Returns key by index

Returns:
-1 if not valid

Definition at line 215 of file fibonacci_heap.hpp.

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.

void link_nodes ( fibonacci_heap_node y,
fibonacci_heap_node x 
) [private]

Links right node to childs of left node

Definition at line 352 of file fibonacci_heap.hpp.

fibonacci_heap& operator= ( const fibonacci_heap fh) [private]

Member Data Documentation

fibonacci_heap_node** A [protected]

supporting array

Definition at line 453 of file fibonacci_heap.hpp.

int Dn [protected]

size of supporting array

Definition at line 456 of file fibonacci_heap.hpp.

int max_num_nodes [protected]

maximum number of nodes

Definition at line 450 of file fibonacci_heap.hpp.

minimal root in heap

Definition at line 438 of file fibonacci_heap.hpp.

fibonacci_heap_node** nodes [protected]

array of nodes for fast search by index

Definition at line 441 of file fibonacci_heap.hpp.

int num_nodes [protected]

number of nodes

Definition at line 444 of file fibonacci_heap.hpp.

int num_trees [protected]

number of trees

Definition at line 447 of file fibonacci_heap.hpp.


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines