大家好，我刚刚对这个图表有疑问。我怎样才能知道哪个节点是根节点，我将如何堆积这样的东西？
谢谢你。
编辑：对不起，当我说 heapify 时，我的意思是做一个最大堆。通常使用常规堆，我会从左到右，从不是叶节点的第一个节点开始向下筛选。我不明白我怎么能在这里做到这一点。
user1870035
问问题
902 次
3 回答
1
这是一个二项式堆，它没有一个根，而是一组根（因为二项式堆是一组二叉树）。
“制作最大堆”是什么意思？最大堆和二项式堆彼此之间的距离就像 java 和 javascript 一样接近。
如果您提取最小 n 次，您可以获得一个最大堆的排序数组。复杂度为 O(n*log(n))。
于 2012-12-09T15:32:13.890 回答
0
从概念上讲，根应该是唯一没有祖先的节点 - 在您的图表中为 1。
于 2012-12-09T04:57:24.810 回答
0
我认为您正在尝试将二项式堆视为二进制堆，这是行不通的。
二进制堆可以存储在没有显式链接的数组中 - 链接隐含在数组中的位置中。一个无序数组可以被“堆化”，重新排序以在 O(n) 时间内生成一个有效的二进制堆。这是二进制堆的一个关键优势——有一个轻量级的实现可以很好地使用内存。
我从来没有实现过二项式堆，虽然我研究过它们，但那是不久前的事了。不过，我非常有信心，二项式堆不是二叉堆，不能以这种方式实现。二项堆有其自身的优势，但它们并没有保留二叉堆的所有优点。如果二项式堆普遍优越，那么没有人会关心二叉堆。
IIRC，二叉树的正常实现（二叉堆所基于）是每个父节点都有一个子节点的链表和一个根的链表。这些链接列表使用显式链接。这就是每个节点支持 k 个子节点的方式，k 没有上限。
二进制堆的重要额外操作是合并。如果二项式堆存储在具有隐式链接的数组中，则合并显然需要大量复制——首先将项目从一个数组复制到另一个数组。因此，有效的合并是不可能的——二项式堆的关键优势将丢失。
然而，对于显式链接，将两个二叉树组合为一个是 O(1) 指针摆弄操作（将一个项目添加到链表的头部），因此两个二叉堆可以与 O(log n) 二叉树合并合并非常有效。
这有点像排序数组和二叉搜索树之间的区别。当然，排序数组有优势，但也有局限性。当您只需修改一个或两个链接而不在数组中移动项目时，某些操作会更有效。有时您不需要这些操作，并且避免需要链接并仅对排序数组进行二进制搜索会更有效，这相当于搜索具有隐式链接的完美平衡的二进制搜索树。
于 2012-12-09T16:13:37.930 回答