我需要证明二叉堆的中位数(不管是最小堆还是最大堆)可以位于堆的最低层(在叶子中)。我不知道如何证明这一点。我考虑过使用堆是完整二叉树这一事实，但我不确定。我该如何证明？
最佳答案
正如 @Evg 在评论中提到的，如果所有元素都相同，那么这是事实。假设所有元素都需要不同，让我们关注奇数个节点 2H+1 和最小堆的情况(最大堆情况类似)。要创建中位数位于底部的最小堆，首先插入最小的 H 元素。
有两种情况。情况1;完成此操作后，由这些 H 元素形成的二叉树被完全填充(每一层都被填充)，然后您可以在最后一层插入剩余的 H+1 个元素(您可以这样做，因为最后一层的最大容量等于( #total_nodes+1)/2 恰好是 H+1)。
情况2 最后一层仍然有一些未填充的空间。在这种情况下，从最大的 H 元素中取出最小的剩余节点，直到填充该层(请注意，堆中不会向上移动，因为这些元素已经比树中的任何元素都大)。然后通过插入中位数开始下一层。最后插入剩余的节点，这些节点也不会向上移动，因为它们通过构造比上层中的任何节点都大。通过对最后一层容量的相同论证，在此过程中您将不需要启动新层。
在节点数为偶数 2H 的情况下，你可以类似地争论，但是你必须将中位数定义为 H+1 最小节点(否则你要证明的陈述是错误的，如你所见注意集合 {1,2} 唯一可能的最小堆是根为 1、叶子为 2 的树。
关于algorithm - 证明堆中位数的水平，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/59546200/