fibonacci_heap Class Reference

#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)

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.

~fibonacci_heap

(

)

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 264 of file fibonacci_heap.hpp.

void cascading_cut ( fibonacci_heap_node *  tree )

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.

void clear_node ( int  index )

private

Clears node by index

Definition at line 384 of file fibonacci_heap.hpp.

void consolidate ( )

private

Consolidates heap

Definition at line 295 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 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)

Returns

item with minimal key

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
	)

Returns key by index

Returns

-1 if not valid

Definition at line 214 of file fibonacci_heap.hpp.

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.

void link_nodes ( fibonacci_heap_node *  y, fibonacci_heap_node *  x  )

private

Links right node to childs of left node

Definition at line 351 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 452 of file fibonacci_heap.hpp.

int Dn

protected

size of supporting array

Definition at line 455 of file fibonacci_heap.hpp.

int max_num_nodes

protected

maximum number of nodes

Definition at line 449 of file fibonacci_heap.hpp.

fibonacci_heap_node* min_root

protected

minimal root in heap

Definition at line 437 of file fibonacci_heap.hpp.

fibonacci_heap_node** nodes

protected

array of nodes for fast search by index

Definition at line 440 of file fibonacci_heap.hpp.

int num_nodes

protected

number of nodes

Definition at line 443 of file fibonacci_heap.hpp.

int num_trees

protected

number of trees

Definition at line 446 of file fibonacci_heap.hpp.

---

The documentation for this class was generated from the following file:

• fibonacci_heap.hpp