Min到Max-Heap，比较

Question

当将min堆转换为具有n节点的最大堆时，我希望找到最大的比较数.我认为用O(n)将min堆转换为max堆。这意味着没有办法重新创建堆。

Answer 1

作为一个粗略的下限，给定一棵具有(min-或max-)堆属性的树，我们不知道叶子上的值是如何相互比较的。在最大堆中，叶子all处的值可能小于内部节点上的所有值。如果堆具有完整二叉树的拓扑结构，那么即使找到最小值也至少需要n/2的比较，其中n是树节点的数目。

Answer 2

如果您有一个已知大小的最小堆，那么您可以通过从后面到前面填充数组来创建其元素的二进制最大堆，方法是迭代地从min堆中删除根节点，直到根节点耗尽为止。在某些情况下，甚至可以做到这一点。使用根节点为元素0，节点i的子节点为元素2i和2i+1的规则，将自动满足由新数组表示的堆的(max-)堆条件。

但是，从大小为m的最小堆中进行的每次删除都需要进行日志(M)元素比较，以恢复堆条件。我认为这意味着整个工作的O(n log n)比较。我怀疑你在不增加条件的情况下，是否能以任何较低的复杂度做这件事。特别是，如果您不执行真正的堆删除(导致恢复堆条件的成本)，那么我认为您将承担相应的额外成本，以确保最终得到堆。