证明堆中位数的水平
proving level of median in heap
我需要证明二叉堆的中位数（不管是最小堆还是最大堆）可以在堆的最低层（在叶子中）。我不确定如何证明这一点。我考虑过使用堆是一个完整的二叉树这一事实，但我不确定。我该如何证明？
正如@Evg 在评论中提到的那样，如果所有元素都相同，那么这很正常。假设所有元素都需要不同，让我们关注节点数量为奇数 2H+1 和最小堆的情况（最大堆情况类似）。要创建中位数在底部的最小堆，首先插入最小的 H 元素。
有两种情况。情况1;这样做之后，由这些 H 元素形成的二叉树被完全填充（每一层都被填充）然后你可以将剩余的 H+1 元素插入最后一层（你可以这样做，因为最后一层的最大容量等于（ #total_nodes+1)/2 正好是 H+1).
案例2 最后一层还有一些空位。在这种情况下，从最大的 H 元素中取出最小的剩余节点，直到该层被填充（请注意，堆中不会向上移动，因为这些元素已经比树中的任何元素都大）。然后通过插入中位数开始下一层。最后插入剩余的节点，它们也不会向上移动，因为它们比上面层中的任何节点都大，通过构造。通过最后一层容量的相同论证，在此过程中您将不需要启动新层。
在偶数个节点2H的情况下，你可以类似地论证，但是你必须将中位数定义为H+1个最小节点（否则你要证明的陈述是错误的，因为你可以通过注意到集合 {1,2} 的唯一可能的最小堆是根在 1 和叶在 2 的树。
证明它的最简单方法就是制作一个：
1
2 3
4 5 6 7
任何具有水平顺序节点的完整堆都将在最左侧的叶子处具有中值，但您不必证明那个。
我需要证明二叉堆的中位数（不管是最小堆还是最大堆）可以在堆的最低层（在叶子中）。我不确定如何证明这一点。我考虑过使用堆是一个完整的二叉树这一事实，但我不确定。我该如何证明？
正如@Evg 在评论中提到的那样，如果所有元素都相同，那么这很正常。假设所有元素都需要不同，让我们关注节点数量为奇数 2H+1 和最小堆的情况（最大堆情况类似）。要创建中位数在底部的最小堆，首先插入最小的 H 元素。
有两种情况。情况1;这样做之后，由这些 H 元素形成的二叉树被完全填充（每一层都被填充）然后你可以将剩余的 H+1 元素插入最后一层（你可以这样做，因为最后一层的最大容量等于（ #total_nodes+1)/2 正好是 H+1).
案例2 最后一层还有一些空位。在这种情况下，从最大的 H 元素中取出最小的剩余节点，直到该层被填充（请注意，堆中不会向上移动，因为这些元素已经比树中的任何元素都大）。然后通过插入中位数开始下一层。最后插入剩余的节点，它们也不会向上移动，因为它们比上面层中的任何节点都大，通过构造。通过最后一层容量的相同论证，在此过程中您将不需要启动新层。
在偶数个节点2H的情况下，你可以类似地论证，但是你必须将中位数定义为H+1个最小节点（否则你要证明的陈述是错误的，因为你可以通过注意到集合 {1,2} 的唯一可能的最小堆是根在 1 和叶在 2 的树。
证明它的最简单方法就是制作一个：
1
2 3
4 5 6 7
任何具有水平顺序节点的完整堆都将在最左侧的叶子处具有中值，但您不必证明那个。