| 1 | <a name="FibonacciHeap"></a>
|
| 2 | ## FibonacciHeap
|
| 3 | * [new FibonacciHeap()](#new_FibonacciHeap_new)
|
| 4 | * _instance_
|
| 5 | * [.insert()](#FibonacciHeap+insert)
|
| 6 | * [.size()](#FibonacciHeap+size)
|
| 7 | * [.clear()](#FibonacciHeap+clear)
|
| 8 | * [.isEmpty()](#FibonacciHeap+isEmpty)
|
| 9 | * [.extractMinimum()](#FibonacciHeap+extractMinimum)
|
| 10 | * [.remove()](#FibonacciHeap+remove)
|
| 11 | * _static_
|
| 12 | * [._decreaseKey()](#FibonacciHeap._decreaseKey)
|
| 13 | * [._cut()](#FibonacciHeap._cut)
|
| 14 | * [._cascadingCut()](#FibonacciHeap._cascadingCut)
|
| 15 | * [._linkNodes()](#FibonacciHeap._linkNodes)
|
| 16 |
|
| 17 | <a name="new_FibonacciHeap_new"></a>
|
| 18 | ### new FibonacciHeap()
|
| 19 | Creates a new instance of a Fibonacci Heap.
|
| 20 |
|
| 21 | <a name="FibonacciHeap+insert"></a>
|
| 22 | ### fibonacciHeap.insert()
|
| 23 | 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.
|
| 24 |
|
| 25 | **Kind**: instance method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 26 | <a name="FibonacciHeap+size"></a>
|
| 27 | ### fibonacciHeap.size()
|
| 28 | Returns the number of nodes in heap. Running time: O(1) actual.
|
| 29 |
|
| 30 | **Kind**: instance method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 31 | <a name="FibonacciHeap+clear"></a>
|
| 32 | ### fibonacciHeap.clear()
|
| 33 | Removes all elements from this heap.
|
| 34 |
|
| 35 | **Kind**: instance method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 36 | <a name="FibonacciHeap+isEmpty"></a>
|
| 37 | ### fibonacciHeap.isEmpty()
|
| 38 | Returns true if the heap is empty, otherwise false.
|
| 39 |
|
| 40 | **Kind**: instance method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 41 | <a name="FibonacciHeap+extractMinimum"></a>
|
| 42 | ### fibonacciHeap.extractMinimum()
|
| 43 | Extracts the node with minimum key from heap. Amortized running
time: O(log n).
|
| 44 |
|
| 45 | **Kind**: instance method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 46 | <a name="FibonacciHeap+remove"></a>
|
| 47 | ### fibonacciHeap.remove()
|
| 48 | Removes 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.
|
| 49 |
|
| 50 | **Kind**: instance method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 51 | <a name="FibonacciHeap._decreaseKey"></a>
|
| 52 | ### FibonacciHeap._decreaseKey()
|
| 53 | 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.
|
| 54 |
|
| 55 | **Kind**: static method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 56 | <a name="FibonacciHeap._cut"></a>
|
| 57 | ### FibonacciHeap._cut()
|
| 58 | The reverse of the link operation: removes node from the child list of parent.
This method assumes that min is non-null. Running time: O(1).
|
| 59 |
|
| 60 | **Kind**: static method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 61 | <a name="FibonacciHeap._cascadingCut"></a>
|
| 62 | ### FibonacciHeap._cascadingCut()
|
| 63 | Performs a cascading cut operation. This cuts node 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.
|
| 64 |
|
| 65 | **Kind**: static method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|
| 66 | <a name="FibonacciHeap._linkNodes"></a>
|
| 67 | ### FibonacciHeap._linkNodes()
|
| 68 | Make the first node a child of the second one. Running time: O(1) actual.
|
| 69 |
|
| 70 | **Kind**: static method of <code>[FibonacciHeap](#FibonacciHeap)</code>
|