algorithm - 证明堆中的中位数水平

Question

我需要证明二叉堆的中位数(无论是最小堆还是最大堆都没有关系)可以在堆的最低级别(在叶中)。我不知道如何证明。我想过使用堆是一个完整的二叉树的事实，但我不确定。我怎样才能证明呢？

Answer 1

正如@Evg 在评论中提到的那样，如果所有元素都相同，则这是微不足道的。假设所有元素都需要不同，让我们关注具有奇数节点 2H+1 和最小堆的情况(最大堆情况类似)。要创建中位数位于底部的最小堆，首先插入最小的 H 元素。

有两种情况。情况1;这样做之后，由这些 H 元素形成的二叉树被完全填充(每一层都被填充)然后你可以在最后一层插入剩余的 H+1 元素(你可以这样做，因为最后一层的最大容量等于( #total_nodes+1)/2 正好是 H+1)。

案例2 最后一层仍有一些未填充的空间。在这种情况下，从最大的 H 元素中取出最小的剩余节点，直到填充该层(请注意，您的堆中不会有向上移动，因为这些元素已经比树中的任何元素都大)。然后通过插入中位数开始下一层。最后插入剩余的节点，这些节点也不会向上移动，因为它们比上面层中的任何节点都大，通过构造。通过关于最后一层容量的相同论点，在此过程中您将不需要启动新层。

在节点数为偶数 2H 的情况下，您可以进行类似的论证，但是您必须将中位数定义为 H+1 最小节点(否则您要证明的陈述是错误的，正如您可以看到的那样集合 {1,2} 唯一可能的最小堆是根在 1 和叶在 2 的树)。