Editing Fibonacci heap (section)

==Performance==
Although Fibonacci heaps look very efficient, they have the following two drawbacks:<ref name=FSST>{{cite journal | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman | last2 = Sedgewick | first2 = Robert | author2-link = Robert Sedgewick (computer scientist) | last3 = Sleator | first3 = Daniel D. | author3-link = Daniel Sleator | last4 = Tarjan | first4 = Robert E. | author4-link = Robert Tarjan | doi = 10.1007/BF01840439 | issue = 1–4 | journal = Algorithmica | pages = 111–129 | title = The pairing heap: a new form of self-adjusting heap | url = https://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf | volume = 1 | year = 1986| s2cid = 23664143 }}</ref>
# They are complicated to implement.
# They are not as efficient in practice when compared with theoretically less efficient forms of heaps.<ref>http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/FibonacciHeaps.pdf, p. 79</ref> In their simplest version, they require manipulation of four pointers per node, whereas only two or three pointers per node are needed in other structures, such as the [[binomial heap]], or [[pairing heap]]. This results in large memory consumption per node and high constant factors on all operations.

Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular, delete-min has linear running time in the worst case). For this reason, Fibonacci heaps and other amortized data structures may not be appropriate for [[real-time computing|real-time systems]].

It is possible to create a data structure which has the same worst-case performance as the Fibonacci heap has amortized performance. One such structure, the [[Brodal queue]],<ref name="bare_url">{{Citation |citeseerx=10.1.1.43.8133 |title=Worst-Case Efficient Priority Queues |year=1996 |author=Gerth Stølting Brodal |journal=Proc. 7th ACM-SIAM Symposium on Discrete Algorithms |publisher=[[Society for Industrial and Applied Mathematics]] |pages=52–58 |isbn=0-89871-366-8 |url=https://archive.org/details/proceedingsofsev0000acms/page/52 }}</ref> is, in the words of the creator, "quite complicated" and "[not] applicable in practice." Invented in 2012, the [[strict Fibonacci heap]]<ref>{{Cite conference |doi=10.1145/2213977.2214082 |title=Strict Fibonacci heaps |conference=Proceedings of the 44th symposium on Theory of Computing - STOC '12 |pages=1177 |year=2012 |last1=Brodal |first1=G. S. L. |last2=Lagogiannis |first2=G. |last3=Tarjan |first3=R. E. |isbn=978-1-4503-1245-5 |url=http://www.cs.au.dk/~gerth/papers/stoc12.pdf }}</ref> is a simpler (compared to Brodal's) structure with the same worst-case bounds. Despite being simpler, experiments show that in practice the strict Fibonacci heap performs slower than more complicated [[Brodal queue]] and also slower than basic Fibonacci heap.<ref>{{Cite book|last1=Mrena|first1=Michal|last2=Sedlacek|first2=Peter|last3=Kvassay|first3=Miroslav|title=2019 International Conference on Information and Digital Technologies (IDT) |chapter=Practical Applicability of Advanced Implementations of Priority Queues in Finding Shortest Paths |date=June 2019|location=Zilina, Slovakia|publisher=IEEE|pages=335–344|doi=10.1109/DT.2019.8813457|isbn=9781728114019|s2cid=201812705}}</ref><ref name=":0">{{cite journal |last1=Larkin |first1=Daniel |last2=Sen |first2=Siddhartha |last3=Tarjan |first3=Robert |date=2014 |title=A Back-to-Basics Empirical Study of Priority Queues |journal=Proceedings of the Sixteenth Workshop on Algorithm Engineering and Experiments |pages=61–72 |arxiv=1403.0252 |bibcode=2014arXiv1403.0252L |doi=10.1137/1.9781611973198.7 |isbn=978-1-61197-319-8 |s2cid=15216766}}</ref> The run-relaxed heaps of Driscoll et al. give good worst-case performance for all Fibonacci heap operations except merge.<ref name="driscoll">{{Cite journal | last1=Driscoll | first1=James R. | last2=Gabow | first2=Harold N. | last3=Shrairman | first3=Ruth | last4=Tarjan | first4=Robert E. | date=November 1988 | title=Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation |journal=Communications of the ACM | volume=31 | issue=11 | pages=1343–1354 | doi=10.1145/50087.50096 | s2cid=16078067 | doi-access=free }}</ref> Recent experimental results suggest that the Fibonacci heap is more efficient in practice than most of its later derivatives, including quake heaps, violation heaps, strict Fibonacci heaps, and rank pairing heaps, but less efficient than pairing heaps or array-based heaps.<ref name=":0" />