特殊的 minHeap 是一个 minHeap，每个级别从左到右排序。在最坏的情况下， 如何n按顺序打印所有元素？O(n)
minHeap 是通过二叉堆实现的，其中的树是一棵完全二叉树（见图）。
下面是一个特殊的 minHeap 的例子：
所以结果应该是：[1,3,4,5,8,10,17,18,20,22,25,30]
来自家庭作业的问题。
问问题
574 次
2 回答
2
如果n是一个与堆大小无关的参数，那么在标准的基于比较的模型下，这是不可能的。您将需要额外的限制，例如比您提到的更多的预先存在的顺序，或者堆的所有元素都是在足够低的范围内的整数。
假设您有一个 height 堆k，其中根及其左孩子链的值分别为 1、2、3、... k。我们可以在不违反“特殊minheap”条件的情况下以任何顺序将>k 的值分配给这些节点的k-1 个右子节点，然后分配大于这些值的值来填充堆的其余部分。打印此堆中的前 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 到 k=log(n) 求和 O(2^k) 得到 O(n)。
于 2016-03-08T19:10:23.550 回答
1
堆的每一层都是按升序排列的。有 log(n) 个级别。
我们可以对级别进行合并，即 O(n log k)。在这种情况下，k 是级别数，或 log(n)，因此我们知道可以在 O(n * log(log n)) 中执行此操作。
这些级别中有 1、2、4、8、16 等节点。第一次合并操作删除了第一层，所以我们的合并堆中的项目数变成了 k-1。在最坏的情况下，在删除一半节点后，合并堆为 k-2，以此类推。
我手头没有数学，但我怀疑解决方案涉及显示扩展系列（即跟踪合并堆大小并乘以通过每个大小堆的节点数）减少到 2，如前所述在评论中。
于 2016-03-08T19:23:04.580 回答