我需要知道二进制和二进制堆之间的主要区别,不管它们的结构差异,二元堆只能有两个子(树表示),二项堆可以有任意数量的子.
我实际上只是想知道组织二项式树结构的特别之处在于第一个孩子在一个节点上有第二个有两个第三个有四个等等吗？
如果我们使用一些普通的树而没有两个孩子的限制然后应用联合过程而只是让一个堆成为其他堆的左子？
algorithm priority-queue binary-heap data-structures binomial-heap
有人可以解释一下我应该如何决定是否使用一个或另一个堆实现,在标题中提到的那些？
根据问题,我想要一个答案来指导我选择有关结构性能的实施方案.现在,我正在做一个优先级队列,但我想知道这个案例最合适的实现,但是基本允许我在任何其他情况下选择一个实现...
另外需要考虑的是我这次使用的是haskell,所以,如果你知道任何可以改善这种语言实现的技巧或其他东西,请告诉我!但和以前一样,欢迎使用其他语言的评论!
谢谢!对不起,如果问题太基础,但我根本不熟悉.这是我第一次面临实施一项任务的任务......
再次感谢!
Okasaki 的Purely Functional Data Structures 中描述的偏斜二项式堆支持在最坏情况下合并O(log (max (m,n)))，其中m和n是要合并的队列的长度。这比在最坏情况下支持它的分段二项式队列和在最坏情况下O(log (min (m,n)))支持它O(log (max (m,n)))但O(log (min (m,n)))分摊时间 [*] 的惰性二项式队列更糟糕。这似乎是队列表示中的偏斜二进制数采用规范形式（只有一个 2，并且仅作为最低有效非零数字）的限制所固有的。是否可以稍微放宽此限制以获得更有效的合并？基本挑战是不允许 2 级联到另一个 2。
[*] 我最近还提出了一种调度二项式队列的变体，其最坏情况边界与分段队列相同；该版本尚未完全实施。
有人可以解释什么是Disjoint Sets Data Structure是什么？或者将我链接到YouTube视频或解释它的文章.
几分钟前我搜索过它,我得到的只是一些数学课程,其中包含一个看起来像维恩图的图像.也许就是这样,但我不确定,所以任何帮助都会受到赞赏.
简而言之,当我被问到"如何使用二叉树来表示二项式队列中的每个二叉树时"这是指你必须相互堆叠的二叉树.就像B1连接B1一样成为B2,那么两个B2成为B3,依此类推.
algorithm binary-tree disjoint-sets data-structures binomial-heap