specal minheap是一个minheap，每个级别都是从左到右排序的。
在最坏的情况下，如何按顺序打印所有n元素？
minHeap由二进制堆实现，其中的树是一个完整的二进制树（见图）。
下面是一个特殊的minheap示例：
所以结果应该是：O(n)
作业中的问题。
最佳答案
如果n是一个独立于堆大小的参数，那么在标准的基于比较的模型下，这是不可能的你需要额外的限制，比如比你提到的更多的预先存在的顺序，或者堆的所有元素都是在足够低的约束下的整数。
假设有一堆高度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））合并，将o（2^k）从k=1求和到k=log（n）得到o（n）。
关于algorithm - 特殊的minHeap，如何打印O(n)中的所有n个元素？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35866708/