Editing Fibonacci heap (section)

== Operations ==
To allow fast deletion and concatenation, the roots of all trees are linked using a circular [[doubly linked list]]. The children of each node are also linked using such a list. For each node, we maintain its number of children and whether the node is marked. 

=== Find-min ===
We maintain a pointer to the root containing the minimum key, allowing <math>O(1)</math> access to the minimum. This pointer must be updated during the other operations, which adds only a constant time overhead.

=== Merge ===
The merge operation simply concatenates the root lists of two heaps together, and setting the minimum to be the smaller of the two heaps. This can be done in constant time, and the potential does not change, leading again to constant amortized time.

=== Insert ===
The insertion operation can be considered a special case of the merge operation, with a single node. The node is simply appended to the root list, increasing the potential by one. The amortized cost is thus still constant.

=== Delete-min ===
[[Image:Fibonacci heap extractmin1.png|thumb|Figure 2. First phase of ''delete-min''.]]
[[File:Fibonacci heap extractmin2.png|thumb|163x163px|Figure 3. Third phase of ''delete-min''.]]
The delete-min operation does most of the work in restoring the structure of the heap. It has three phases:

# The root containing the minimum element is removed, and each of its <math>d</math> children becomes a new root. It takes time <math>O(d)</math> to process these new roots, and the potential increases by <math>d-1</math>. Therefore, the amortized running time of this phase is <math>O(d) = O(\log n)</math>.
# There may be up to <math>n</math> roots. We therefore decrease the number of roots by successively linking together roots of the same degree. When two roots have the same degree, we make the one with the larger key a child of the other, so that the minimum heap property is observed. The degree of the smaller root increases by one. This is repeated until every root has a different degree. To find trees of the same degree efficiently, we use an array of length <math>O(\log n)</math> in which we keep a pointer to one root of each degree. When a second root is found of the same degree, the two are linked and the array is updated. The actual running time is <math>O(\log n + m)</math>, where <math>m</math> is the number of roots at the beginning of the second phase. In the end, we will have at most <math>O(\log n)</math> roots (because each has a different degree). Therefore, the difference in the potential from before to after this phase is <math>O(\log n) - m</math>. Thus, the amortized running time is <math>O(\log n + m) + c(O(\log n) - m)</math>. By choosing a sufficiently large <math>c</math> such that the terms in <math>m</math> cancel out, this simplifies to <math>O(\log n)</math>.
# Search the final list of roots to find the minimum, and update the minimum pointer accordingly. This takes <math>O(\log n)</math> time, because the number of roots has been reduced.
Overall, the amortized time of this operation is <math>O(\log n)</math>, provided that <math>d = O(\log n)</math>. The proof of this is given in the following section.

=== Decrease-key ===
[[Image:Fibonacci heap-decreasekey.png|246x246px|thumb|Figure 4. Fibonacci heap from Figure 1 after decreasing key of node 9 to 0.]]If decreasing the key of a node <math>x</math> causes it to become smaller than its parent, then it is cut from its parent, becoming a new unmarked root. If it is also less than the minimum key, then the minimum pointer is updated.

We then initiate a series of ''cascading cuts'', starting with the parent of <math>x</math>. As long as the current node is marked, it is cut from its parent and made an unmarked root. Its original parent is then considered. This process stops when we reach an unmarked node <math>y</math>. If <math>y</math> is not a root, it is marked. In this process we introduce some number, say <math>k</math>, of new trees. Except possibly <math>x</math>, each of these new trees loses its original mark. The terminating node <math>y</math> may become marked. Therefore, the change in the number of marked nodes is between of <math>-k</math> and <math>-k+2</math>. The resulting change in potential is <math>k+2(-k+2)=-k+4</math>. The actual time required to perform the cutting was <math>O(k)</math>. Hence, the amortized time is <math>O(k) + c(-k+4)</math>, which is constant, provided <math>c</math> is sufficiently large.