FibonacciHeap

Make-heap: creates a new empty heap.

To make an empty Fibonacci heap, the MAKE-FIB-HEAP procedure allocates and returns the Fibonacci heap object H, where H.n = 0 and H.min = NIL ; there are no trees in H. Because t(H) = 0 and m(H) = 0, the potential of the empty Fibonacci heap is pot(H) = 0. The amortized cost of MAKE-FIB-HEAP is thus equal to its O(1) actual cost.

We access a given Fibonacci heap H by a pointer H.min to the root of a tree containing the minimum key; we call this node the minimum node of the Fibonacci heap. If more than one root has a key with the minimum value, then any such root may serve as the minimum node. When a Fibonacci heap H is empty, H.min is NIL.

FIB-HEAP-DECREASE-kEY:

Delete ref must be internal ref.prev and ref.next get reset to null

Find-min: simply return the top element of the heap.

Minimum: return a pointer to the element whose key is minimum

The minimum node of a Fibonacci heap H is given by the pointer H.min, so we can find the minimum node in O(1) actual time. Because the potential of H does not change, the amortized cost of this operation is equal to its O(1) actual cost.

Increase-key: remove the item at the key to be increased, replace the key with a larger key, then push the result back into the heap.

Union: Uniting two Fibonacci heaps

The following procedure unites Fibonacci heaps H_1 and H_2, destroying H_1 and H_2 in the process. It simply concatenates the root lists of H_1 and H_2 and then determines the new minimum node. Afterward, the objects representing H_1 and H_2 will never be used again.

/!\ Assumes the same comparison function is used in both trees.

Change in potential is zero. Amortized cost is O(1), the actual cost.

Synonym for FibonacciHeap#meld. TODO Remove this.

FIB-HEAP-EXTRACT-MIN(H):

Extracting the minimum node

The process of extracting the minimum node is the most complicated of the operations presented in this section. It is also where the delayed work of consolidating trees in the root list finally occurs. The following pseudocode extracts the minimum node. The code assumes for convenience that when a node is removed from a linked list, pointers remaining in the list are updated, but pointers in the extracted node are left unchanged. It also calls the auxiliary procedure CONSOLIDATE, which we shall see shortly.

Create a new node for the inserted element and put it into the heap.

Insert: insert new node. /!\ ref.next = ref.prev = ref which means all references that are external to the tree must reset .next and .prev and one must not call FibonacciHeap#pushreference with an internal reference from this tree or another, except the root of another tree.

Change in potential is 1. Therefore amortized cost is O(1).