二叉堆、二项式堆和斐波那契堆之间有什么区别？
What is the difference between binary, binomial, and Fibonacci heaps?
我想知道二叉堆、二叉堆和斐波那契堆之间的基本区别，以及它们最适用于哪些场景。
我主要关心他们在 Dijkstra 算法中的应用，它的时间复杂度如何根据使用的堆类型而变化？
根据维基百科，二叉堆 是使用二叉树创建的堆数据结构。可以看做是一棵二叉树加上两个附加约束完全二叉树和堆属性。请注意，堆 属性 是所有节点都大于或小于每个子节点。
二叉堆比大多数二叉堆复杂。但是，它具有出色的合并性能，时间复杂度为 O(lg N)。二项式堆由二项式树的列表组成。
在进入 Fibonacci 堆 之前，最好先探索一下为什么我们甚至需要它们。还有很多其他类型的堆（例如二叉堆和二项式堆），那么为什么我们需要另一种堆？
主要原因在Dijkstra算法和Prim算法上。这两种图算法都通过维护一个优先级队列来工作，该队列包含具有关联优先级的节点。有趣的是，这些算法依赖于称为 decrease-key 的堆操作，该操作采用优先级队列中已有的条目，然后降低其键值（即增加其优先级）。事实上，这些算法的很多运行时间都可以通过调用 decrease-key 的次数来解释。如果我们可以构建一个优化 decrease-key 的数据结构，我们就可以优化这些算法的性能。在二叉堆和二项式堆的情况下，减少键需要时间 O(log n)，其中 n 是优先级队列中的节点数。如果我们可以将其降低到 O(1)，那么 Dijkstra 算法和 Prim 算法的时间复杂度将从 O(m log n) 降低到 (m + n log n)，这比以前更快了。因此，尝试构建一个高效支持reduce-key的数据结构是有意义的。
如果您有兴趣了解有关 Fibonacci 堆的更多信息，您可能需要查看这个由两部分组成的系列讲座幻灯片。 Part one introduces binomial heaps and shows how lazy binomial heaps work.Part two 探索斐波那契堆。这些幻灯片比我在这里介绍的更深入数学。
我想知道二叉堆、二叉堆和斐波那契堆之间的基本区别，以及它们最适用于哪些场景。 我主要关心他们在 Dijkstra 算法中的应用，它的时间复杂度如何根据使用的堆类型而变化？
根据维基百科，二叉堆 是使用二叉树创建的堆数据结构。可以看做是一棵二叉树加上两个附加约束完全二叉树和堆属性。请注意，堆 属性 是所有节点都大于或小于每个子节点。
二叉堆比大多数二叉堆复杂。但是，它具有出色的合并性能，时间复杂度为 O(lg N)。二项式堆由二项式树的列表组成。
在进入 Fibonacci 堆 之前，最好先探索一下为什么我们甚至需要它们。还有很多其他类型的堆（例如二叉堆和二项式堆），那么为什么我们需要另一种堆？
主要原因在Dijkstra算法和Prim算法上。这两种图算法都通过维护一个优先级队列来工作，该队列包含具有关联优先级的节点。有趣的是，这些算法依赖于称为 decrease-key 的堆操作，该操作采用优先级队列中已有的条目，然后降低其键值（即增加其优先级）。事实上，这些算法的很多运行时间都可以通过调用 decrease-key 的次数来解释。如果我们可以构建一个优化 decrease-key 的数据结构，我们就可以优化这些算法的性能。在二叉堆和二项式堆的情况下，减少键需要时间 O(log n)，其中 n 是优先级队列中的节点数。如果我们可以将其降低到 O(1)，那么 Dijkstra 算法和 Prim 算法的时间复杂度将从 O(m log n) 降低到 (m + n log n)，这比以前更快了。因此，尝试构建一个高效支持reduce-key的数据结构是有意义的。
如果您有兴趣了解有关 Fibonacci 堆的更多信息，您可能需要查看这个由两部分组成的系列讲座幻灯片。 Part one introduces binomial heaps and shows how lazy binomial heaps work.Part two 探索斐波那契堆。这些幻灯片比我在这里介绍的更深入数学。