特殊minHeap，如何在O(n) 中打印所有n 个元素？
special minHeap, how to print all the n elements in O(n)?
Speical minHeap是每层从左到右排序的minHeap。
在最坏的情况下，如何按 O(n) 中的顺序打印所有 n 元素？
minHeap是通过二叉堆实现的，其中的树是一棵完全二叉树（见图）。
这里是一个特殊的 minHeap 的例子：
所以结果应该是：[1,3,4,5,8,10,17,18,20,22,25,30]
家庭作业问题。
如果n是一个独立于堆大小的参数，那么在标准的基于比较的模型下，这是不可能的。您将需要额外的限制，例如比您提到的更多的预先存在的顺序，或者堆的所有元素都是足够低的整数。
假设您有一个高度为 k 的堆，其中根及其左子节点链的值为 1、2、3 ... k。我们可以在不违反 "special minheap" 条件的情况下，以任意顺序为这些节点的 k-1 个右子节点分配 >k 的值，然后分配大于这些节点的值来填充堆的其余部分。打印此堆中的前 2k-1 个值需要对 k-1 个值进行排序，这些值可以按任何顺序排列，这无法在少于 O(k*log(k)) 时间内通过比较完成。
如果n 应该是堆的大小，这很简单。堆不变量是不必要的；只对图层进行排序很重要。 mergesort 合并第一层和第二层，然后将每个连续层合并到已经合并的结果中，将花费 O(n) 时间。第 k 次合并将 2^k-1 个已经合并的元素与来自下一层的 <=2^k 个元素合并，花费 O(2^k) 时间。有 O(log(n)) 合并，从 k=1 到 k=log(n) 的 O(2^k) 求和得到 O(n).
堆的每一层都按升序排列。有 log(n) 个级别。
我们可以合并级别，这是 O(n log k)。 k 在这种情况下是级别数，或 log(n)，因此我们知道可以在 O(n * log(log n)).
中执行此操作
关卡中有 1、2、4、8、16 等节点。第一个合并操作删除了第一层，因此合并堆中的项目数变为 k-1。在最坏的情况下，删除一半节点后，合并堆为k-2，等等
我手头没有数学知识，但我怀疑解决方案涉及证明扩展系列（即跟踪合并堆大小并乘以通过每个大小堆的节点数）减少到 2，如评论中所述。
Speical minHeap是每层从左到右排序的minHeap。
在最坏的情况下，如何按 O(n) 中的顺序打印所有 n 元素？
minHeap是通过二叉堆实现的，其中的树是一棵完全二叉树（见图）。
这里是一个特殊的 minHeap 的例子：
所以结果应该是：[1,3,4,5,8,10,17,18,20,22,25,30]
家庭作业问题。
如果n是一个独立于堆大小的参数，那么在标准的基于比较的模型下，这是不可能的。您将需要额外的限制，例如比您提到的更多的预先存在的顺序，或者堆的所有元素都是足够低的整数。
假设您有一个高度为 k 的堆，其中根及其左子节点链的值为 1、2、3 ... k。我们可以在不违反 "special minheap" 条件的情况下，以任意顺序为这些节点的 k-1 个右子节点分配 >k 的值，然后分配大于这些节点的值来填充堆的其余部分。打印此堆中的前 2k-1 个值需要对 k-1 个值进行排序，这些值可以按任何顺序排列，这无法在少于 O(k*log(k)) 时间内通过比较完成。
如果n 应该是堆的大小，这很简单。堆不变量是不必要的；只对图层进行排序很重要。 mergesort 合并第一层和第二层，然后将每个连续层合并到已经合并的结果中，将花费 O(n) 时间。第 k 次合并将 2^k-1 个已经合并的元素与来自下一层的 <=2^k 个元素合并，花费 O(2^k) 时间。有 O(log(n)) 合并，从 k=1 到 k=log(n) 的 O(2^k) 求和得到 O(n).
堆的每一层都按升序排列。有 log(n) 个级别。
我们可以合并级别，这是 O(n log k)。 k 在这种情况下是级别数，或 log(n)，因此我们知道可以在 O(n * log(log n)).
中执行此操作关卡中有 1、2、4、8、16 等节点。第一个合并操作删除了第一层，因此合并堆中的项目数变为 k-1。在最坏的情况下，删除一半节点后，合并堆为k-2，等等
我手头没有数学知识，但我怀疑解决方案涉及证明扩展系列（即跟踪合并堆大小并乘以通过每个大小堆的节点数）减少到 2，如评论中所述。