com.mxgraph.analysis

Class mxFibonacciHeap

java.lang.Object

com.mxgraph.analysis.mxFibonacciHeap

public class mxFibonacciHeap
extends java.lang.Object

This class implements a priority queue.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	mxFibonacciHeap.Node Implements a node of the Fibonacci heap.

Constructor Summary

Constructors

Constructor and Description
mxFibonacciHeap()

Method Summary

Modifier and Type	Method and Description
void	decreaseKey(mxFibonacciHeap.Node x, double k) Decreases the key value for a heap node, given the new value to take on.
void	delete(mxFibonacciHeap.Node x) Deletes a node from the heap given the reference to the node.
mxFibonacciHeap.Node	getNode(java.lang.Object element, boolean create) Returns the node that represents element.
void	insert(mxFibonacciHeap.Node node, double key) Inserts a new data element into the heap.
boolean	isEmpty() Returns true if the queue is empty.
mxFibonacciHeap.Node	min() Returns the smallest element in the heap.
mxFibonacciHeap.Node	removeMin() Removes the smallest element from the heap.
int	size() Returns the size of the heap which is measured in the number of elements contained in the heap.
static mxFibonacciHeap	union(mxFibonacciHeap h1, mxFibonacciHeap h2) Joins two Fibonacci heaps into a new one.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

mxFibonacciHeap

public mxFibonacciHeap()

Method Detail

getNode

public mxFibonacciHeap.Node getNode(java.lang.Object element,
                                    boolean create)

Returns the node that represents element.

Parameters:

element - the element whose node to find

create - whether to create

Returns:

the node representing the specified element

isEmpty

public boolean isEmpty()

Returns true if the queue is empty.

Returns:

whether the queue is empty

decreaseKey

public void decreaseKey(mxFibonacciHeap.Node x,
                        double k)

Decreases the key value for a heap node, given the new value to take on. The structure of the heap may be changed and will not be consolidated.

Running time: O(1) amortized

Parameters:

x - Node whose value should be decreased.

k - New key value for node x.

Throws:

java.lang.IllegalArgumentException - Thrown if k is larger than x.key value.

delete

public void delete(mxFibonacciHeap.Node x)

Deletes a node from the heap given the reference to the node. The trees in the heap will be consolidated, if necessary. This operation may fail to remove the correct element if there are nodes with key value -Infinity.

Running time: O(log n) amortized

Parameters:

x - The node to remove from the heap.

insert

public void insert(mxFibonacciHeap.Node node,
                   double key)

Inserts a new data element into the heap. No heap consolidation is performed at this time, the new node is simply inserted into the root list of this heap.

Running time: O(1) actual

Parameters:

node - new node to insert into heap

key - key value associated with data object

min

public mxFibonacciHeap.Node min()

Returns the smallest element in the heap. This smallest element is the one with the minimum key value.

Running time: O(1) actual

Returns:

Returns the heap node with the smallest key.

removeMin

public mxFibonacciHeap.Node removeMin()

Removes the smallest element from the heap. This will cause the trees in the heap to be consolidated, if necessary. Does not remove the data node so that the current key remains stored.

Running time: O(log n) amortized

Returns:

Returns the node with the smallest key.

size

public int size()

Returns the size of the heap which is measured in the number of elements contained in the heap.

Running time: O(1) actual

Returns:

Returns the number of elements in the heap.

union

public static mxFibonacciHeap union(mxFibonacciHeap h1,
                                    mxFibonacciHeap h2)

Joins two Fibonacci heaps into a new one. No heap consolidation is performed at this time. The two root lists are simply joined together.

Running time: O(1) actual

Parameters:

h1 - The first heap.

h2 - The second heap.

Returns:

Returns a new heap containing h1 and h2.