JGraph
v5.13.0.0


com.jgraph.algebra
Class JGraphFibonacciHeap

java.lang.Object
  extended by com.jgraph.algebra.JGraphFibonacciHeap

public class JGraphFibonacciHeap
extends Object

This class implements a priority queue.


Nested Class Summary
static class JGraphFibonacciHeap.Node
          Implements a node of the Fibonacci heap.
 
Field Summary
protected  JGraphFibonacciHeap.Node min
           
protected  Map nodes
          Maps from elements to nodes
protected  int size
           
 
Constructor Summary
JGraphFibonacciHeap()
           
 
Method Summary
protected  void cascadingCut(JGraphFibonacciHeap.Node y)
          Performs a cascading cut operation.
protected  void consolidate()
          Consolidates the trees in the heap by joining trees of equal degree until there are no more trees of equal degree in the root list.
protected  void cut(JGraphFibonacciHeap.Node x, JGraphFibonacciHeap.Node y)
          The reverse of the link operation: removes x from the child list of y.
 void decreaseKey(JGraphFibonacciHeap.Node x, double k)
          Decreases the key value for a heap node, given the new value to take on.
 void delete(JGraphFibonacciHeap.Node x)
          Deletes a node from the heap given the reference to the node.
 JGraphFibonacciHeap.Node getNode(Object element, boolean create)
          Returns the node that represents element.
 void insert(JGraphFibonacciHeap.Node node, double key)
          Inserts a new data element into the heap.
 boolean isEmpty()
           
protected  void link(JGraphFibonacciHeap.Node y, JGraphFibonacciHeap.Node x)
          Make node y a child of node x.
 JGraphFibonacciHeap.Node min()
          Returns the smallest element in the heap.
 JGraphFibonacciHeap.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 JGraphFibonacciHeap union(JGraphFibonacciHeap h1, JGraphFibonacciHeap h2)
          Joins two Fibonacci heaps into a new one.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

nodes

protected Map nodes
Maps from elements to nodes


min

protected JGraphFibonacciHeap.Node min

size

protected int size
Constructor Detail

JGraphFibonacciHeap

public JGraphFibonacciHeap()
Method Detail

getNode

public JGraphFibonacciHeap.Node getNode(Object element,
                                        boolean create)
Returns the node that represents element.


isEmpty

public boolean isEmpty()

decreaseKey

public void decreaseKey(JGraphFibonacciHeap.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 to decrease the key of
k - new key value for node x
Throws:
IllegalArgumentException - Thrown if k is larger than x.key value.

delete

public void delete(JGraphFibonacciHeap.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 - node to remove from heap

insert

public void insert(JGraphFibonacciHeap.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 JGraphFibonacciHeap.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:
heap node with the smallest key

removeMin

public JGraphFibonacciHeap.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:
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:
number of elements in the heap

union

public static JGraphFibonacciHeap union(JGraphFibonacciHeap h1,
                                        JGraphFibonacciHeap 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 - first heap
h2 - second heap
Returns:
new heap containing h1 and h2

cascadingCut

protected void cascadingCut(JGraphFibonacciHeap.Node y)
Performs a cascading cut operation. This cuts y from its parent and then does the same for its parent, and so on up the tree.

Running time: O(log n); O(1) excluding the recursion

Parameters:
y - node to perform cascading cut on

consolidate

protected void consolidate()
Consolidates the trees in the heap by joining trees of equal degree until there are no more trees of equal degree in the root list.

Running time: O(log n) amortized


cut

protected void cut(JGraphFibonacciHeap.Node x,
                   JGraphFibonacciHeap.Node y)
The reverse of the link operation: removes x from the child list of y. This method assumes that min is non-null.

Running time: O(1)

Parameters:
x - child of y to be removed from y's child list
y - parent of x about to lose a child

link

protected void link(JGraphFibonacciHeap.Node y,
                    JGraphFibonacciHeap.Node x)
Make node y a child of node x.

Running time: O(1) actual

Parameters:
y - node to become child
x - node to become parent

JGraph
v5.13.0.0


Copyright (C) 2001-2009 JGraph Ltd. All rights reserved.