从数组创建二项式堆？
Creating a binomial heap from an array?
创建二项堆时，我知道一般的过程是先创建一个指向nil的头，然后慢慢插入1节点堆，并根据4种情况合并相同度数的堆。
但是，我想问给定一个大小为n的数组，是否有可能因为最多有floor(lg n) + 1个二叉树，我们根据树的数量对数组进行划分，2 ^0、2^1、2^2 等等，并且在每棵二叉树中冒泡，以便每棵树都满足最小堆 属性?
例如：
给定数组 [4, 10, 8, 20, 5, 1, 3]
- 如果一条一条插入，根表为3、1、4。1有child5； 4 有 child 8 和 10 和 8 有 child 20.
- 在另一种情况下：我们有根列表 4、8 和 1。8 有 child 10； 1 有 child 3 和 20，3 有 child 5.
如果这样做，是否会破坏二项式堆的全部目的？
看来你在这里有三个不同的问题。
- 您能否使用您描述的方法从数组构建二项式堆？
- 从过程中返回不同的二项式堆与将元素一次一个地添加到空二项式堆中得到的二项式堆是否有问题？
- 这样做值得吗？
让我们逐一检查。
这种方法行得通吗？
是的！这是构建二项式堆的完全有效的方法。二项式堆的规则只要求 (1) 没有两棵树的大小相同，并且 (2) 每棵树都是 heap-ordered。因此，从这个意义上说，任何将您从元素集合带入 heap-ordered 不同大小的二叉树集合的过程都将起作用。
我们没有得到相同的堆是不是很糟糕？
不，这根本不是问题。你是对的，如果你继续这样做，你会得到不同的二项式堆。但是你也可以通过以不同的顺序从数组中添加元素来获得不同的堆。例如，如果您使用正常的插入算法并按排序顺序添加原始数组中的元素，您将获得的堆的形状将与从左到右进行的堆的形状不同。 （并且该堆的形状与您从右到左得到的堆的形状不同。）通过类比二叉堆进行推理 - 您可以有许多不同的二叉堆，它们都具有相同的元素，只是顺序不同.
这值得吗？
与二叉堆相比，二叉堆有两个优点：
- 将 n 个值的序列一次插入一个空的二项式堆中需要时间 O(n) worst-case；一次将 n 个元素插入一个空的二叉堆中可能需要花费 Θ(n log n) 的时间。
- 它们支持高效融合。您可以在 O(log n) 时间内合并两个二项堆，而二叉堆则需要时间 O(n)。
在您所描述的情况下，所有元素都已提前提供给您，优势 (1) 不相关，因为您还可以在时间 O(n) 内使用这些元素构建二叉堆heapify 算法。
同样，如果您选择使用隐式数组表示法来表示二项式堆，您将失去进行快速合并的能力，因为快速合并操作需要使用指针和链接单元格来表示树，这样对象就不会链接时不需要在内存中移动
所以总的来说，我想说这是一个非常酷的见解，你正在考虑这个很好，但从效率的角度来看，这本身可能不值得。
话虽这么说，但有些数据结构确实使用了隐式堆，这些堆由使用相同原理的多棵树构成。 smoothsort 算法使用 Leonardo 堆，它使用与二项式堆相似但不相同的结构，后来的工作引入了具有另一种类似结构的杨树堆。弱堆使用隐式表示，与您在此处提出的建议相差不远。
创建二项堆时，我知道一般的过程是先创建一个指向nil的头，然后慢慢插入1节点堆，并根据4种情况合并相同度数的堆。
但是，我想问给定一个大小为n的数组，是否有可能因为最多有floor(lg n) + 1个二叉树，我们根据树的数量对数组进行划分，2 ^0、2^1、2^2 等等，并且在每棵二叉树中冒泡，以便每棵树都满足最小堆 属性?
例如： 给定数组 [4, 10, 8, 20, 5, 1, 3]
- 如果一条一条插入，根表为3、1、4。1有child5； 4 有 child 8 和 10 和 8 有 child 20.
- 在另一种情况下：我们有根列表 4、8 和 1。8 有 child 10； 1 有 child 3 和 20，3 有 child 5.
如果这样做，是否会破坏二项式堆的全部目的？
看来你在这里有三个不同的问题。
- 您能否使用您描述的方法从数组构建二项式堆？
- 从过程中返回不同的二项式堆与将元素一次一个地添加到空二项式堆中得到的二项式堆是否有问题？
- 这样做值得吗？
让我们逐一检查。
这种方法行得通吗？
是的！这是构建二项式堆的完全有效的方法。二项式堆的规则只要求 (1) 没有两棵树的大小相同，并且 (2) 每棵树都是 heap-ordered。因此，从这个意义上说，任何将您从元素集合带入 heap-ordered 不同大小的二叉树集合的过程都将起作用。
我们没有得到相同的堆是不是很糟糕？
不，这根本不是问题。你是对的，如果你继续这样做，你会得到不同的二项式堆。但是你也可以通过以不同的顺序从数组中添加元素来获得不同的堆。例如，如果您使用正常的插入算法并按排序顺序添加原始数组中的元素，您将获得的堆的形状将与从左到右进行的堆的形状不同。 （并且该堆的形状与您从右到左得到的堆的形状不同。）通过类比二叉堆进行推理 - 您可以有许多不同的二叉堆，它们都具有相同的元素，只是顺序不同.
这值得吗？
与二叉堆相比，二叉堆有两个优点：
- 将 n 个值的序列一次插入一个空的二项式堆中需要时间 O(n) worst-case；一次将 n 个元素插入一个空的二叉堆中可能需要花费 Θ(n log n) 的时间。
- 它们支持高效融合。您可以在 O(log n) 时间内合并两个二项堆，而二叉堆则需要时间 O(n)。
在您所描述的情况下，所有元素都已提前提供给您，优势 (1) 不相关，因为您还可以在时间 O(n) 内使用这些元素构建二叉堆heapify 算法。
同样，如果您选择使用隐式数组表示法来表示二项式堆，您将失去进行快速合并的能力，因为快速合并操作需要使用指针和链接单元格来表示树，这样对象就不会链接时不需要在内存中移动
所以总的来说，我想说这是一个非常酷的见解，你正在考虑这个很好，但从效率的角度来看，这本身可能不值得。
话虽这么说，但有些数据结构确实使用了隐式堆，这些堆由使用相同原理的多棵树构成。 smoothsort 算法使用 Leonardo 堆，它使用与二项式堆相似但不相同的结构，后来的工作引入了具有另一种类似结构的杨树堆。弱堆使用隐式表示，与您在此处提出的建议相差不远。