我正在实现Fibonacci堆，以改进我的Dijkstra最短路径算法。我的insert方法运行得很好，我需要做的下一个方法是extract-min。我正在关注CLRS。请注意，书中提到的一些属性还没有出现在我的实现中，因为到目前为止函数还不需要它们，但我稍后会添加它们。private static class FibonacciHeap {
* Implementation of the node used in
* fibonaccipublic int
浏览 28提问于2020-04-10得票数 0
回答已采纳
1回答
我有这个Prim Algo的MST实现，它是|V|的3次方。但CLRS表示，假设|V| ~ |E| it O(|V| * lg |V|)，复杂度为O (E * lg |V| )。我的实现可能是固定的，但我不确定如何使用矩阵实现在|V| * |V|下面{ int** v;public
浏览 0提问于2013-06-29得票数 0
回答已采纳
删除元素后，擦除操作是否也更新堆？我在fibonacci_heap的boost文档中对成员函数进行了解释，其中提到了在增加/减少操作之后会发生什么，但是当涉及到擦除时，唯一声明的是擦除句柄所指向的元素。这是否意味着在那之后堆会被改造呢？如果不是，被擦除的节点的子节点会发生什么情况？我漏掉了什么明显的东西吗？
浏览 3提问于2015-03-09得票数 3
回答已采纳
3回答
我知道，我知道它的实现，但我总是跳过我现在想问的一个部分。的算法实现是O(E + V log(V))和，我的问题是：
如何用Fibonacci堆实现Prim的算法？
浏览 6提问于2011-01-28得票数 21
回答已采纳
我需要描述一个算法，它使用操作: Insert、ExtractMin、DecreaseKey和GetMin在Fibonacci中找到第二个最小的元素。最后一个是以前实现的查找和返回堆中最小元素的算法。
我想我应该从提取最小值开始，这样它的孩子就会生根。然后，我可以使用GetMin找到第二个最小的元素。
浏览 0提问于2013-01-11得票数 1
回答已采纳
我试图使用最小优先级队列(使用Fibonacci堆实现)来确定dijkstra算法的运行时间。密码
分析:我知道对于Fibonacci堆插入是减少/插入键是O(1)，而提取min是O(log(n))第4行中的循环采用O(V)，但是ExtractMin
浏览 1提问于2014-02-27得票数 0
回答已采纳
1回答
在n-element Fibonacci堆上执行-element的实际最长时间是多少？它是O(D(n) + t(H))吗，其中D(n) = lg*n是n元素堆中节点的最大度，t(H) = O(n)是堆H中的许多根？
这是否意味着上述问题的答案实际上是O(n) = Theta(n)？
浏览 0提问于2014-02-10得票数 0
回答已采纳
是否有用于Haskell的Fibonacci堆/优先级队列？(甚至是渐近线更好的？)我在中找到了各种优先级队列实现的列表，但是我找不到它们是否满足Fibonacci堆的摊销运行时间：
找到-最小是O(1)摊销时间。
浏览 1提问于2013-05-29得票数 11
回答已采纳
1回答
我试图实现Dijkstra的算法，使用Fibonacci Heap来查找节点之间的最短路径，并对图进行邻接列表表示。根据我所知道的算法，我们必须在堆中找到最小节点，然后遍历它的所有邻居并更新它们的距离。但是要获得邻居的当前距离(存储在堆中的每个节点中)，我必须从堆中查找特定节点的。“‘Find”操作需要O(N)时间，其中N是Fibonacci堆中的节点数。那么，我的算法是正确的，还是我遗漏了什么？任何帮助都将不胜感激。
浏览 2提问于2015-04-08得票数 1
1回答
我一直试图理解Fibonacci实现代码，并尝试用简单的测试用例进行测试，这似乎不起作用。我插入了3个节点，然后每次打印最小值，但答案是错误的。实现是错误的还是我没有正确理解代码？* * @return The smallest element of the
浏览 2提问于2015-04-08得票数 0
回答已采纳
3回答
我正在研究不同类型的堆数据结构。另外，在java.util中有斐波那契堆的实现吗
谢谢!
浏览 26提问于2011-06-08得票数 36
回答已采纳
我知道Dijkstra算法的步骤顺序如下：
继续这样做，直到我们得到目标顶点，否则就找不到其他顶点了。到目前为止，我已经看到了两种类型的实现，一种是使用最小堆O(log )来获得最小顶点，另一种是使用简单循环(O( V) )。我的问题是，如果使用
浏览 3提问于2022-06-01得票数 0
回答已采纳
1回答
如果我们构造基于RB树和堆的排序集。执行insertion()和deleteMax() n次。
(1)。什么是Big-O？我的想法是:对于RB树和堆，deleteMax()和insertion()都需要nlog(n)，那么这是否意味着时间复杂度将是O(nlog(n) + nlog(n)) = O(2nlog(n))？
浏览 0提问于2013-06-17得票数 0
1回答
使用Fibonacci堆时Dijkstra比二进制堆快吗？我自己完成了一些实现斐波纳契堆的实验，并在Dijkstra中使用它，我还检查了使用模糊堆库中准备使用的Fibonacci堆，但是没有一个实现能够更快地使用二进制堆找到最短路径。在Dijsktra中查找最短路径的上下文中，Fibonacci堆实际上比二进制堆慢吗？
浏览 8提问于2022-07-06得票数 2
1回答
我试图了解fibonacci堆，在堆中插入元素的伪代码是：degree[x] := 0child[x] := NIL Fibonacci-Heap-Extract-Min(H) if x <> NIL n[H] := n
浏览 4提问于2013-01-11得票数 1
回答已采纳
1回答
新的“堆”boost库包括一个fibonacci堆。每个实现的复杂性可以在这里看到：。
我的问题是:为什么fibonacci堆减少操作O(log(N))，而增加操作是O(1)？我想尝试在Dijkstra的算法中使用fibonacci堆，该算法在很大程度上依赖于快速减少操作。
浏览 0提问于2012-10-02得票数 4
2回答
通过使用二进制最小堆实现最小优先级队列，可以对算法进行改进。
所以我想知道，为什么要发表这样的声明？仅仅对优先级队列使用堆不是总是更明智的吗？
浏览 4提问于2013-09-26得票数 1
我在一个初学者级别的计算机编程课上，我(和其他3个学生)想在期末项目中实现一个斐波那契堆。有没有人能推荐一些fibonacci堆的好应用？一些足够华丽的东西可以作为很好的演示材料？
浏览 10提问于2012-03-03得票数 1
云服务器
ICP备案
对象存储
腾讯会议
云直播
腾讯云开发者
