二进制堆和斐波那契堆的真实世界中的应用 [英] 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.

编辑：添加了二进制堆也。想知道。

EDITED: 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.

从维基：

虽然一个总运行时间   开始操作序列   空结构由界   界上面给出一些（很少）   序列中的操作可以采取   很长时间才能完成（具体   删除和删除最小具有线性   在最坏的情况下运行的时间）。对于   为此斐波那契堆等   摊销数据结构可能不   适合于实时系统。

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算法（最小生成树）和霍夫曼编码（数据通信pression）。

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屋！