Fibonacci_Heap Class Reference

Fibonacci heap. More...

Classes
class	Node
	Basic class the fibonacci heap is composed of. More...

Public Member Functions
function	GetAuthor ()
function	GetName ()
function	GetShortName ()
function	GetDescription ()
function	GetVersion ()
function	GetDate ()
function	CreateInstance ()
function	GetCategory ()
constructor	Fibonacci_Heap ()
	Create a new fibonacci heap.
function	Insert (item, priority)
	Insert a new entry in the heap.
function	Pop ()
	Pop the first entry of the list.
function	Peek ()
	Peek the first entry of the list.
function	Count ()
	Get the amount of current items in the list.
function	Exists (item)
	Check if an item exists in the list.
function	ExistsIn (list, item)
	Auxilary function to search through the whole heap.

Public Attributes
	_min = null
	_min_index = 0
	_min_priority = 0
	_count = 0
	_root_list = null

Detailed Description

Fibonacci heap.

This heap is heavily optimized for the Insert and Pop functions. Peek and Pop always return the current lowest value in the list. Insert is implemented as a lazy insert, as it will simply add the new node to the root list. Sort is done on every Pop operation.

Constructor & Destructor Documentation

constructor Fibonacci_Heap::Fibonacci_Heap ( )

inline

Create a new fibonacci heap.

http://en.wikipedia.org/wiki/Fibonacci_heap

Member Function Documentation

function Fibonacci_Heap::Count

(

)

Get the amount of current items in the list.

The complexity of this operation is O(1).

Returns

The amount of items currently in the list.

function Fibonacci_Heap::Exists

(

item

)

Check if an item exists in the list.

The complexity of this operation is O(n).

Parameters

item	The item to check for.

Returns

True if the item is already in the list.

function Fibonacci_Heap::ExistsIn	(	list	,
		item
	)

Auxilary function to search through the whole heap.

Parameters

list	The list of nodes to look through.
item	The item to search for.

Returns

True if the item is found, false otherwise.

function Fibonacci_Heap::Insert	(	item	,
		priority
	)

Insert a new entry in the heap.

The complexity of this operation is O(1).

Parameters

item	The item to add to the list.
priority	The priority this item has.

function Fibonacci_Heap::Peek

(

)

Peek the first entry of the list.

This is always the item with the lowest priority. The complexity of this operation is O(1).

Returns

The item of the entry with the lowest priority.

function Fibonacci_Heap::Pop

(

)

Pop the first entry of the list.

This is always the item with the lowest priority. The complexity of this operation is O(ln n).

Returns

The item of the entry with the lowest priority.

---

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

• library.nut
• main.nut