二元堆和斐波那契堆的实际应用 [英] Real world applications of Binary heaps and Fibonacci Heaps

问题描述

斐波那契堆和二元堆在现实世界中的应用是什么?如果你能分享一些你用它解决问题的例子，那就太好了.

What are the real world applications of Fibonacci heaps and binary heaps? It'd be great if you could share some instance when you used it to solve a problem.

还添加了二进制堆.很想知道.

Added binary heaps also. Curious to know.

推荐答案

您在现实生活中很少会用到.我相信斐波那契堆的目的是改善 Dijkstra 算法的渐近运行时间.对于非常非常大的输入，它可能会给您带来改进，但在大多数情况下，您只需要一个简单的二叉堆.

You would rarely use one in real life. I believe the purpose of the Fibonacci heap was to improve the asymptotic running time of Dijkstra's algorithm. It might give you an improvement for very, very large inputs, but most of the time, a simple binary heap is all you need.

来自维基:

虽然a的总运行时间开始的操作序列空结构由上面给出的界限，一些(很少)序列中的操作可以采取很长时间才能完成(特别是删除和删除最小值具有线性最坏情况下的运行时间).为了这个原因斐波那契堆和其他摊销数据结构可能不是适用于实时系统.

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 and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

二叉堆是一种数据结构，可用于快速查找一组值中的最大值(或最小值).它用于 Dijkstra 算法(最短路径)、Prim 算法(最小生成树)和 Huffman 编码(数据压缩).

The binary heap is a data structure that can be used to quickly find the maximum (or minimum) value in a set of values. It's used in Dijkstra's algorithm (shortest path), Prim's algorithm (minimum spanning tree) and Huffman encoding (data compression).

这篇关于二元堆和斐波那契堆的实际应用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！