如果你有一个大小为14的二项堆，你怎么知道哪个节点是根节点？

enter image description here 如果你有一个大小为14的二项堆，你怎么知道哪个节点是根节点？

嗨，大家好，我只是有一个关于这个图的问题。如何判断哪个节点是根节点，并且我该如何heapify这样的事情？

谢谢。

编辑：对不起，当我说heapify我的意思是做一个最大的堆。通常有一个常规的堆，我会从左到右，从第一个不是叶节点的节点开始向下筛选。虽然我没有看到我能做到这一点。

来源

2012-12-09 CoffeeIsProgramming

我不确定你在问什么。在一般情况下，二项堆不是一棵树，它是一棵树的集合。它没有“根节点”。即使它碰巧是一棵树，它也应该已经被堆砌，根节点是最小的关键节点。这全部由Binomial Heap定义。 – AnT

我认为你想把二项堆看作一个二进制堆，这是行不通的。

A Binary Heap可以存储在一个没有显式链接的数组中 - 链接隐含在数组中的位置。无序数组可以“堆积”，重新排序以在O（n）时间内生成有效的二进制堆。这是二进制堆的关键优势 - 有一个使用内存的轻量级实现。

我从来没有实施过Binomial Heap，尽管我已经研究过它们，那是前一阵子。不过，我非常自信，二项堆不是二进制堆，不能以这种方式实现。二项堆有其自身的优势，但它们并没有保留二元堆的所有优点。如果二项堆普遍优越，那么没有人会关心二元堆。

IIRC，二项式树的正常实现（基于二项堆）是每个父节点和一个链表的根链接列表。这些链接列表使用显式链接。这就是你如何支持每个节点的k个孩子，没有k的上限。

二进制堆的重要额外操作是合并。如果二项堆被存储在一个带隐式链接的数组中，合并显然需要大量的复制 - 将一个数组中的项目复制到另一个数组中以便开始。因此，高效的合并是不可能的 - 二项堆的关键优势将会丧失。但是，将两个二叉树组合成一个是O（1）指针操作（将项添加到链表的头部），因此可以将两个二项式堆合并为O（log n）二项树非常有效地合并。

这有点像排序数组和二叉搜索树之间的区别。当然，排序后的数组有优势，但也有局限性。如果您只需修改一个或两个链接而不移动数组中的项目，则某些操作效率更高。有时候你不需要这些操作，而且避免链接的需要和二进制搜索排序数组的效率更高，这相当于用隐式链接搜索完美平衡的二叉搜索树。

来源

2012-12-09 16:13:37 Steve314

概念上，根应该是唯一没有祖先的节点 - 在图的情况下为1。

来源

2012-12-09 04:57:24

这是一个二项堆，它没有一个根，而是一组根（因为二项堆是一组二叉树）。

你是什么意思“做一个最大的堆”？最大的堆和二项堆是相互靠得很近，因为java和javascript是。

如果您提取最少n次，您可以获得一个最大堆的排序数组。复杂度为O（n * log（n））。

来源

2012-12-09 15:32:13 Thomash

“最大堆”是*任何*堆，其中最高优先级项目是最大（最大）项目。这可能是一个二叉堆，就像它可能是一个二进制堆一样容易。最大。与最小。堆独立于堆数据结构。也就是说，从最小堆变为最大堆是微不足道的（交换'<' for '>'），所以不要相信Adam真的在问他在问什么。尽管如此，关于排序数组的点也是+1。 – Steve314

如果你有一个大小为14的二项堆，你怎么知道哪个节点是根节点？

回答

相关问题