1

在创建二项式堆时，我知道一般程序是首先创建一个指向 nil 的头，然后慢慢插入 1 节点堆，并根据 4 种情况将具有相同程度的堆联合起来。

但是，我想问一下，给定一个大小为 n 的数组，是否有可能由于最多有 floor(lg n) + 1 个二叉树，我们根据树的数量对数组进行分区，2^0, 2^ 1, 2^2 以此类推，在每棵二叉树中冒泡，使得每棵树都满足 minheap 属性？

例如：给定数组 [4, 10, 8, 20, 5, 1, 3]

  1. 如果一个一个插入，根列表是3、1和4。1有子5；4 有孩子 8 和 10，8 有孩子 20。
  2. 在另一种情况下：我们有根列表 4、8 和 1。8 有子 10；1 有孩子 3 和 20，3 有孩子 5。

如果以这种方式完成，它会破坏二项式堆的全部目的吗？

4

1 回答 1

1

看来您在这里有三个单独的问题。

  1. 您可以使用您描述的方法从数组构建二项式堆吗？
  2. 如果您一次将元素添加到一个空的二项式堆中，那么您从过程中得到不同的二项式堆是否是一个问题？
  3. 这是值得做的事情吗？

让我们一次一个地检查它们。

这种方法有效吗？

是的！这是构建二项式堆的一种完全有效的方法。二项式堆的规则只要求 (1) 没有两棵大小相同的树和 (2) 每棵树都是堆排序的。所以从这个意义上说，任何让你从元素集合到不同大小的堆排序二叉树集合的过程都可以工作。

我们没有得到相同的堆是不是很糟糕？

不，这根本不是问题。你是对的，如果你这样做，你会得到不同的二项式堆。但是你也可以通过以不同的顺序从数组中添加元素来获得不同的堆。例如，如果您使用正常的插入算法并按排序顺序添加原始数组中的元素，那么您将获得的堆与从左到右进行的堆具有不同的形状。（并且该堆的形状与您通过从右到左进行的形状不同。）通过类比二叉堆进行推理 - 您可以拥有许多不同的二叉堆，它们都具有相同的元素，只是顺序不同.

这值得吗？

与二叉堆相比，二叉堆有两个优点：

  1. 在最坏的情况下，一次将一个 n 值序列插入一个空的二项式堆需要时间 O(n)；一次将 n 个元素插入一个空的二进制堆可能需要时间 Θ(n log n)。
  2. 它们支持高效融合。您可以在 O(log n) 时间内合并两个二项式堆，而使用二项式堆则需要 O(n) 时间。

在您所描述的情况下，所有元素都预先提供给您，优势（1）不相关，因为您还可以使用 heapify 算法在时间 O(n) 中从这些元素构建二进制堆。

类似地，如果您选择使用隐式数组表示来表示二项式堆，您将失去进行快速融合的能力，因为快速融合操作需要使用指针和链接单元格来表示树，以便不需要移动对象链接时在内存中。

所以总的来说，我想说这是一个非常酷的见解，你考虑这个很好，但从效率的角度来看，这本身可能不值得。

话虽如此，有些数据结构确实使用由使用相同原理的多棵树组成的隐式堆。Smoothsort算法使用Leonardo heaps，其结构与二项式堆相似但又不同，后来的工作引入了具有另一种类似结构的poplar heap。弱堆使用隐式表示，与您在此处提出的建议相距不远。

于 2020-11-01T19:09:28.597 回答