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.

  - ### Field Summary

    Fields
    Modifier and Type | Field and Description
    --- | ---
    `protected mxFibonacciHeap.Node` | `min`
    `protected java.util.Map<java.lang.Object,mxFibonacciHeap.Node>` | `nodes` Maps from elements to nodes
    `protected int` | `size`

  - ### Constructor Summary

    Constructors
    Constructor and Description
    `mxFibonacciHeap()`

  - ### Method Summary

    Methods
    Modifier and Type | Method and Description
    --- | ---
    `protected void` | `cascadingCut(mxFibonacciHeap.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(mxFibonacciHeap.Node x, mxFibonacciHeap.Node y)` The reverse of the link operation: removes x from the child list of y.
    `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.
    `protected void` | `link(mxFibonacciHeap.Node y, mxFibonacciHeap.Node x)` Make node y a child of node x.
    `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

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Field Detail

    - #### nodes

          protected java.util.Map<java.lang.Object,mxFibonacciHeap.Node> nodes

      Maps from elements to nodes

    - #### min

          protected mxFibonacciHeap.Node min

    - #### size

          protected int size

  - ### Constructor Detail

    - #### mxFibonacciHeap

          public mxFibonacciHeap()

  - ### Method Detail

    - #### getNode

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

      Returns the node that represents element.

    - #### isEmpty

          public boolean isEmpty()

      Returns true if 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.

    - #### cascadingCut

          protected void cascadingCut(mxFibonacciHeap.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` - The 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(mxFibonacciHeap.Node x,
                 mxFibonacciHeap.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` - The child of y to be removed from y's child list.
        `y` - The parent of x about to lose a child.

    - #### link

          protected void link(mxFibonacciHeap.Node y,
                  mxFibonacciHeap.Node x)

      Make node y a child of node x.

      Running time: O(1) actual

      Parameters:
        `y` - The node to become child.
        `x` - The node to become parent.

Copyright (c) 2010 Gaudenz Alder. All rights reserved.