The degree of Fibonacci heaps

The Fibonacci heap is a priority queue data structure in which finding and removing the top-priority item takes logarithmic time (like a binary heap) but reprioritizing items to have higher priority takes only constant time, under amortized time analysis. This property is useful for speeding up the time complexity of algorithms including Dijkstra’s algorithm for shortest paths and Jarník’s algorithm for minimum spanning trees, so that they take logarithmic time per vertex and constant time per edge. In its internal structure, the Fibonacci heap is a forest of trees, with one tree node per prioritized object, higher priorities towards to roots of the trees. The analysis of its logarithmic-time find-and-remove operation can be split into two parts: showing that the time of this operation is proportional to the maximum number of children of any node in this tree (the degree of the node), and showing that the degree is logarithmic. It is the second part of this analysis that gives the…