Editing Fibonacci heap (section)

=== 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.