斐波纳契堆和二进制堆在现实世界中有哪些应用?如果在解决问题时可以共享一些实例,那就太好了。
编辑:还 添加了二进制堆。好奇地知道。
您很少会在现实生活中使用它。我相信斐波那契堆的目的是为了改善Dijkstra算法的渐近运行时间。它可能会为非常非常大的输入带来改进,但是在大多数情况下,您只需要一个简单的二进制堆即可。
从Wiki:
尽管以空结构开始的一系列操作的总运行时间受上述限制,但是该序列中的某些(很少)操作可能需要很长时间才能完成(特别是删除和删除最小值在运行时具有线性运行时间)。最坏的情况)。因此,斐波那契堆和其他摊销数据结构可能不适用于实时系统。
二进制堆是一种数据结构,可用于快速找到一组值中的最大值(或最小值)。它用在Dijkstra的算法(最短路径),Prim的算法(最小生成树)和Huffman编码(数据压缩)中。