Editing Fibonacci heap (section)

== Structure ==
[[Image:Fibonacci heap.png|thumbnail|upright=1.05|Figure 1. Example of a Fibonacci heap. It has three trees of degrees 0, 1 and 3. Three vertices are marked (shown in blue). Therefore, the potential of the heap is 9 (3&nbsp;trees + 2&nbsp;&times;&nbsp;(3&nbsp;marked-vertices)).]]
A Fibonacci heap is a collection of [[tree data structure|tree]]s satisfying the [[minimum-heap property]], that is, the key of a child is always greater than or equal to the key of the parent. This implies that the minimum key is always at the root of one of the trees. Compared with binomial heaps, the structure of a Fibonacci heap is more flexible. The trees do not have a prescribed shape and in the extreme case the heap can have every element in a separate tree. This flexibility allows some operations to be executed in a [[lazy evaluation|lazy]] manner, postponing the work for later operations. For example, merging heaps is done simply by concatenating the two lists of trees, and operation ''decrease key'' sometimes cuts a node from its parent and forms a new tree.

However, at some point order needs to be introduced to the heap to achieve the desired running time. In particular, degrees of nodes (here degree means the number of direct children) are kept quite low: every node has degree at most <math>\log n</math> and the size of a subtree rooted in a node of degree <math>k</math> is at least <math>F_{k+2}</math>, where <math>F_i</math> is the <math>i</math>th [[Fibonacci number]]. This is achieved by the rule: at most one child can be cut off each non-root node. When a second child is cut, the node itself needs to be cut from its parent and becomes the root of a new tree (see Proof of degree bounds, below). The number of trees is decreased in the operation ''delete-min'', where trees are linked together.

As a result of a relaxed structure, some operations can take a long time while others are done very quickly. For the [[amortized analysis|amortized running time]] analysis, we use the [[potential method]], in that we pretend that very fast operations take a little bit longer than they actually do. This additional time is then later combined and subtracted from the actual running time of slow operations. The amount of time saved for later use is measured at any given moment by a potential function. The potential <math>\phi</math> of a Fibonacci heap is given by

:<math>\phi = t + 2m</math>,

where <math>t</math> is the number of trees in the Fibonacci heap, and <math>m</math> is the number of marked nodes. A node is marked if at least one of its children was cut, since this node was made a child of another node (all roots are unmarked). The amortized time for an operation is given by the sum of the actual time and <math>c</math> times the difference in potential, where ''c'' is a constant (chosen to match the constant factors in the [[big O notation]] for the actual time).

Thus, the root of each tree in a heap has one unit of time stored. This unit of time can be used later to link this tree with another tree at amortized time 0. Also, each marked node has two units of time stored. One can be used to cut the node from its parent. If this happens, the node becomes a root and the second unit of time will remain stored in it as in any other root.