c#中的Fibonacci,Binary或Binomial堆？
在计算机科学中，堆是一种特殊的数据结构，它是一种完全二叉树，其每个节点都有一个与之关联的值。堆的性质是每个节点的值要么大于（最大堆）要么小于（最小堆）其子节点的值。
Fibonacci堆是一种特殊的数据结构，它是由Fredman和Tarjan在1984年提出的。Fibonacci堆是一种用于优先级队列的高效数据结构，它支持合并操作、插入操作、查找最小元素操作和删除最小元素操作。Fibonacci堆的优势在于它的合并操作和查找最小元素操作的时间复杂度为O(1)。
Binary堆，也称为二项堆，是一种特殊的数据结构，它是由Brodal和Klein在1996年提出的。Binary堆是一种用于优先级队列的高效数据结构，它支持插入操作、查找最小元素操作和删除最小元素操作。Binary堆的优势在于它的查找最小元素操作的时间复杂度为O(1)。
Binomial堆是一种特殊的数据结构，它是由Brodal和Klein在1996年提出的。Binomial堆是一种用于优先级队列的高效数据结构，它支持插入操作、查找最小元素操作和删除最小元素操作。Binomial堆的优势在于它的插入操作和查找最小元素操作的时间复杂度为O(log n)。
推荐的腾讯云相关产品和产品介绍链接地址：
相关·内容
3回答
在二进制堆中删除
data-structures、priority-queue、binary-heap
我只是在尝试学习二进制堆，并对在二进制堆中执行删除操作有疑问。我读到我们可以从二进制堆中删除一个元素，我们需要重新堆积它。
但在下面的链接中，它显示不可用：
Binary Search AVL Tree Binary Heap (min) Binomial Queue (min)
Find O(log n) O(log n) unavailable unavailable
Delete element O(log n O(log n) unavailable u
浏览 2提问于2011-09-28得票数 6
回答已采纳
4回答
二进制堆和Fibonacci堆的实际应用
algorithm、data-structures、binary-heap、fibonacci-heap
Fibonacci堆和二进制堆的实际应用是什么？如果您可以在使用它来解决问题时共享一些实例，那就太好了。
编辑：也添加了二进制堆。很想知道。
浏览 6提问于2010-09-22得票数 37
回答已采纳
3回答
Boost:优先级队列，支持在O(log )时间内找到一个元素
c++、boost
我很好奇Boost是否提供了优先级队列实现，它也支持在O(log )时间内找到元素？
我可以通过使用Boost Fibonacci堆来实现此功能，并将句柄与它们的索引一起存储在std::map中，并在堆插入时更新此信息，但我希望有一个已经提供此功能的堆版本。
注意:我删除了问题的前一个版本，因为它太含糊了。
浏览 0提问于2014-06-25得票数 4
3回答
将minheap.top移动到maxheap.top，其中maxheap.top <= minheap.top
c++、algorithm、data-structures
我有一个max堆和min堆，其中max堆的最大元素小于或等于min堆的最小元素。
现在，我希望将min堆的最小元素移动为max堆的最大元素。
要做到这一点，一种方法是弹出min堆的顶部元素并将其推到max堆上。
有没有更有效的方法来做到这一点？
，这是我最后做的
实际上，我必须在min堆中插入一个元素，然后执行上面描述的操作，我执行了以下操作：
// place value to insert at end of minheap
mintoph[mintoph_size] = R;
// use std::pop_heap, minimum element now at end
pop_he
浏览 9提问于2012-07-06得票数 0
回答已采纳
1回答
以O(log(n))复杂度更改二进制堆元素的优先级
c++、algorithm、data-structures、heap、time-complexity
我已经写了一个二进制堆来存储优先级类(私有成员是优先级和键)。我想知道当给定变量的键时，如何才能以低于O(n)的复杂度改变堆元素的优先级。提前感谢
浏览 1提问于2015-01-07得票数 0
2回答
二进制堆中更新的时间复杂度是多少？
big-o、time、heap
对于二进制堆，插入有O(log(n))，删除min有O(log(n))，堆构造可以在O(n)中完成。
在使用Djikstra中的二进制堆的上下文中，我的试卷涉及堆中的一个“更新”，其中更改了顶点的优先级。
我假设这个更新的时间复杂性将是O(n)，因为在我看来，在堆中定位顶点需要按照线性搜索的顺序，然后是上堆或下堆。这将是O(n + log(n))，它就是O(n)。
不幸的是，我认为这使我得出了错误的答案。
那么，二进制堆中优先级更新的实际时间复杂度是多少？
浏览 0提问于2015-11-16得票数 9
3回答
我们是否有与其他操作一样复杂的支持删除操作的优先级队列？
algorithm、data-structures、priority-queue
优先级队列因从集合中检索max或min元素而闻名。优先级队列上的两个常见操作是插入和我们是否有支持删除(X)的优先级队列？Delete(x)的含义是两个，从优先级队列中删除项目x。
要做到这一点，最简单的方法是找到项目x并删除它，但是这需要线性时间。我在找一些更好的算法。
浏览 3提问于2014-09-10得票数 3
4回答
如何更新Dijkstra算法中松弛顶点的键？
algorithm、graph、dijkstra
就像被问到的那样，我不明白如何在堆中找到一个松弛顶点的索引。
就编程风格而言，heap是一个黑匣子，它抽象出优先级队列的细节。现在，如果我们需要维护一个哈希表，将顶点键映射到堆数组中的相应索引，那么这需要在heap实现中完成，对吗？
但是大多数标准堆没有提供执行这种映射的哈希表。
处理整个问题的另一种方法是将放松的顶点添加到堆中，而不考虑任何事情。当我们提取最小值时，我们会得到最好的一个。为了防止同一顶点被多次提取，我们可以对访问的顶点进行标记。
因此，我的确切问题是，处理这个问题的典型方式是什么？
比较我提到的方法的利弊是什么？
浏览 8提问于2014-01-15得票数 3
回答已采纳
4回答
键值变化的优先级队列
java、c++、algorithm、data-structures
我必须模拟优先级队列。队列中的键是定期更改的。队列必须能够:添加元素和删除元素。最好的方法是什么(具有最好的复杂性)？最好的数据结构是什么？
浏览 3提问于2011-10-26得票数 0
1回答
我可以使用什么数据结构来实现带有log(n)插入和查找的双结束优先级队列？
algorithms、implementations
如何实现具有插入、查找最小和查找最大操作的O(log(n))复杂性的双结束优先级队列？
我想用一棵红色的黑树，但它有点复杂。还有更简单的选择吗？
我也听说过双端堆，但是查找或删除min和max的复杂性似乎是线性的，而不是对数的。
浏览 0提问于2015-05-05得票数 0
1回答
二进制、二项式和斐波那契堆之间有什么区别？
data-structures、heap、dijkstra
我想知道二进制、二项式和Fibonacci堆之间的基本区别，以及它们最适合使用的场景。我主要关注的是他们在Dijkstra算法中的应用，根据所使用的堆的类型，它的时间复杂度将如何变化？
浏览 1提问于2015-11-20得票数 2
回答已采纳
7回答
具有find功能的优先级队列-最快的实现
optimization、types、heap、binary-tree、priority-queue
我正在考虑实现一个具有附加要求的优先级队列，一个查找/搜索功能，它将告诉您一个项目是否在队列中的任何位置。所以函数是: insert、del-min和find。
我不确定我应该使用堆还是自平衡二叉树。似乎PQ通常是使用堆实现的，但我想知道使用二叉树是否有任何优势，因为我还需要那个find函数。
此外，平均而言，我将执行更多的插入操作而不是删除操作。我也在考虑。基本上，每一秒都很重要。
谢谢!
浏览 0提问于2010-10-20得票数 14
1回答
找到第二大元素。面试的两个变量与优先级队列
arrays、algorithm、heap
经典的面试问题是“在数组中找到第二大元素”。
最直接的方法是跟踪诸如largest、secondLargest和迭代、O(n)时间复杂度和O(1)空间复杂度等变量。
另一种选择是使用堆大小2(或K)实现优先级队列，并在迭代后获取堆元素。对于每次迭代，我将队列大小增加到2，因此时间复杂度为O(n*log(K))，其中K为2，因此在技术上是O(n)。
以下是双方的论点：
两个变量：
简单循环
考虑超越k=2是一个“您不需要它(YAGNI)”的问题。
一些O(n)是更好的解，如果它需要较少的计算。
优先级队列：
堆的开销是存在的，它影响着时间复杂度的系数。但在复杂性分析中，我
浏览 1提问于2022-06-06得票数 0
2回答
具有prim's的堆结构
algorithm、structure、heap、prims-algorithm
我想问一下，用prim算法使用堆结构的兴趣是什么？在分配中：“由于您实现的堆结构将用于Prim的算法”谢谢！
浏览 0提问于2017-04-13得票数 1
回答已采纳
2回答
如何为Prim算法更新堆中的元素优先级？
algorithm、data-structures、heap、minimum-spanning-tree、prims-algorithm
我正在研究Prim的算法。在代码中有一个部分，穿过切割的下一个顶点将到达属于MST的顶点集。在这样做的同时，我们还必须“更新其他集合中与离开的顶点相邻的所有顶点”。这是来自CLRS的快照
有趣的部分在第11行，但是因为我们在这里使用的是堆，所以我们只能访问最小的元素，对吗(heap[0])？那么，我们如何从堆中搜索和更新顶点，即使它们不是最小的顶点，因此我们知道它们的位置，除非通过线性搜索？
浏览 0提问于2013-06-13得票数 12
回答已采纳
5回答
编程竞赛最好的单源最短路径算法是什么？
c++、algorithm、graph
我是从UVa问题集中做的。这是一个没有负边权重的单源最短路径问题。据我所知，对于此类问题，具有最佳大O运行时间的算法是Dijkstra，使用斐波那契堆作为优先级队列，尽管实际上二进制堆更容易实现，并且工作得也很好。
然而，似乎即使是二进制堆也需要相当长的时间才能滚动，而且在比赛中时间是有限的。我知道STL提供了一些堆算法和优先级队列，但它们似乎没有提供Dijkstra需要的减键函数。还是我说错了？
似乎另一种可能性是不使用Dijkstra的，有人声称他们用广度优先搜索/贝尔曼-福特解决了上面的问题，这更容易编码。(编辑: OTOH，Dijkstra的优先级队列超时的未排序数组。)BFS/Bel
浏览 4提问于2009-12-08得票数 1
回答已采纳
2回答
什么时候使用堆作为优先级队列是个坏主意？
algorithm、heap、priority-queue
在解释Dijkstra算法的章节中，在Cormen等人的“算法简介”一书中。在分析算法的复杂性时，他们说
如果图是足够稀疏的..。通过使用二进制最小堆实现最小优先级队列，可以对算法进行改进。
所以我想知道，为什么要发表这样的声明？仅仅对优先级队列使用堆不是总是更明智的吗？
浏览 4提问于2013-09-26得票数 1
6回答
二进制堆是二叉树还是链表？
c、data-structures、tree、linked-list
我有一个实现二进制堆的任务。但是，我不确定是否应该将二进制堆实现为二叉树数据结构还是简单的双链接列表。
如果我应该实现为二叉树，我应该如何跟踪树的最后一个元素，以便插入一个新元素？在链接列表中，这要容易得多。
那么，二进制堆必须是二叉树吗？如果是，如何跟踪最后一个元素？
注意:在我的赋值中有这样的语句：，但是您将实现二进制堆，不是作为数组，而是作为树。。
更清楚的是，这是我的节点：
struct Word{
char * word;
int count;
struct Word * parent;
struct Word * left_child;
st
浏览 9提问于2012-02-18得票数 3
回答已采纳
2回答
是堆和优先级队列、数据结构还是抽象数据类型？
javascript、java、data-structures、adt
我见过类似的问题，也读过很多答案。有人会认为我当时会知道，但有些答案是矛盾的，现在我比我开始时更加困惑。
我的探索开始于as -堆和优先级队列之间的区别是什么？在这里，我了解到Heap是一种数据结构，优先级队列是一种抽象的数据类型。但是为什么呢？
到目前为止，我发现这个答案是最好的：简单地说，数据结构和抽象数据类型之间的关系与算法和伪码之间的关系是一样的。第一个是一个想法，第二个是一个正式的描述(抽象的，不可访问的)。
有些人提到ADT是一个依赖于语言的术语。因为它描述了“标准库中没有包含的数据类型”。因此，在Java或JS中，堆并不在标准库中，但我以前了解到堆是一种数据结构，而不是抽象数据类
浏览 11提问于2020-03-01得票数 0
回答已采纳
2回答
Dijkstra on Java:使用斐波那契堆与PriorityQueue获得有趣的结果
java、data-structures、heap、dijkstra、fibonacci-heap
我最近使用两种数据结构初步比较了Dijkstra算法的运行时间，这两种数据结构是基于Java的PriorityQueue (如果我没有记错的话，它基于二进制堆)和斐波那契堆。我使用Java语言的currentTimeMillis()进行计算。我最终得到的结果非常有趣。这是我的一个测试用例的输出：
Running Dijkstra's with 8 nodes and 27 links
- Execution time with binary heap: 1 miliseconds
- Execution time with Fibonacci heap: 4 miliseconds
诚
浏览 17提问于2013-04-04得票数 5
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频活动推荐
腾讯云开发者
