特殊的小根堆，如何在O(n)时间复杂度内打印出所有n个元素？

Question

特殊小根堆是一种每个层级从左到右排序的小根堆。如何在最坏情况下以O(n)的时间复杂度按顺序打印所有n个元素？该小根堆由二叉堆实现，其中树是完全二叉树（见图）。以下是特殊小根堆的示例：

因此，结果应为：[1,3,4,5,8,10,17,18,20,22,25,30] 作业问题。

- user3781974

---

你可能需要澄清你正在使用哪种数据结构来存储堆。 - ilim

显然不是 MergeSort，因为 MergeSort 的时间复杂度为 O(nlogn)。 - Alaa M.

@alaa-m 考虑从根开始。由于3是最小的元素，您应该将其作为下一个元素。然后，在下一步中，由于4是4、5和17中最小的，您将选择4。然后，您必须在20和25之间做出决定，而您本应选择5。考虑到这一点，我不认为答案那么简单明了。 - ilim

我非常确定在这个结构中，最坏的情况下你需要维护 O(n) 个“指针”。决定前进哪一个将需要 O(log n) 次比较。由于你需要进行 O(n) 次操作，如果你能让运行时间低于 O(n log n)，那我会感到惊讶。 - Vincent van der Weele

@AlaaM：你的答案是正确的，使用了O(n)（实际上是2n）的解决方案。 - Jim Mischel

Answer 1

如果n是一个独立于堆大小的参数，则在标准的基于比较模型下，这是不可能的。你需要额外的限制，比如更多预先存在的顺序，或者所有堆元素都是整数且在足够低的范围内。

假设你有一个高度为k的堆，根节点及其所有左孩子的链表值分别为1、2、3、...k。我们可以按任意顺序为这些节点的k-1个右孩子分配值>k，而不违反“特殊最小堆”条件，然后分配大于这些值的值来填充余下的堆。在此堆中打印前2k-1个值需要对可能按任意顺序排列的k-1个值进行排序，这不能在少于O(k*log(k))的时间内通过比较完成。

如果n应该是堆的大小，则很简单。堆不变式是不必要的；它只关注层次结构是否排序。将第一层和第二层合并，然后将每个连续层次合并到已经合并的结果中的归并排序将花费O(n)的时间。第k个归并将2^k-1个已归并元素与下一层的<=2^k个元素合并，需要O(2^k)的时间。有O(log(n))个归并，将k从1到log(n)的O(2^k)相加得到O(n)。

- user2357112

---

这就是我心中所想的论点，但有时minHeap的定义要求它是一棵完全二叉树（就像示例中那样）。所以我仍然不确定。 - WhatsUp

@WhatsUp：这个参数使用了完全二叉树，所以我不确定你遇到了什么问题。 - user2357112

完整的堆将有约2^k个节点，因此该问题需要在O(2^k)时间内打印出所有节点。这仍然略有不同，与在O(k)时间内打印出前2k-1个值。 - WhatsUp

@WhatsUp：根据问题描述，我认为n是一个与堆大小无关的参数。 - user2357112

啊哈，我曾将其理解为节点的总数，就像他的例子中一样。 - WhatsUp

Answer 2

每个堆的级别都是按升序排列的。共有log(n)个级别。

我们可以对这些级别进行合并，时间复杂度为O(n log k)。在这种情况下，k是级别数或log(n)，因此我们知道可以在O(n * log(log n))内完成。

这些级别中有1、2、4、8、16等节点。第一次合并操作会删除第一个级别，因此我们合并堆中的项目数变为k-1。在最坏情况下，当一半的节点被删除后，合并堆为k-2等等。

我手头没有数学公式，但我怀疑解决方案涉及展开系列（即跟踪合并堆大小并乘以通过每个大小堆的节点数），如评论所述，将其减少到2。

- Jim Mischel

---

我认为这是正确的答案。通过从上到下合并，实际上可以实现O(n)的复杂度，因为每个层级的大小形成了一个公比为2的等比数列。 - WhatsUp

这是O(n)。数学相对简单；我已经在我的答案中做过了。 - user2357112