二叉最大堆的中位数总是叶节点吗？
Is the median of a binary max-heap always a leaf node?
如果我有一个二叉最大堆（一个几乎完整的带有最大堆的二叉树 属性），那么中位数是否总是一个叶节点？我找到了一些这样的例子，但还没有找到反例——尽管到目前为止这还不足以让我正式证明它。
即对于值集 {1,2,3,4,5}，其中中值为 [3]，树将是：
5
/ \
4 [3]
/ \
2 1
所以在这种情况下，中位数是叶节点。
不，它并不总是叶节点。您可以轻松地重新排列示例来证明这一点。另一个使用相同项目的有效最大堆是：
5
/ \
[3] 4
/ \
2 1
考虑 7 个项目的完整最大堆：
7
6 [4]
1 5 3 2
这是一个有效的最大堆。最大的项目在根，所有的子节点都小于它们的父节点。
从这两个例子应该很清楚，你不能假设堆中的中位数总是叶节点。
如果我有一个二叉最大堆（一个几乎完整的带有最大堆的二叉树 属性），那么中位数是否总是一个叶节点？我找到了一些这样的例子，但还没有找到反例——尽管到目前为止这还不足以让我正式证明它。
即对于值集 {1,2,3,4,5}，其中中值为 [3]，树将是：
5
/ \
4 [3]
/ \
2 1
所以在这种情况下，中位数是叶节点。
不，它并不总是叶节点。您可以轻松地重新排列示例来证明这一点。另一个使用相同项目的有效最大堆是：
5
/ \
[3] 4
/ \
2 1
考虑 7 个项目的完整最大堆：
7
6 [4]
1 5 3 2
这是一个有效的最大堆。最大的项目在根，所有的子节点都小于它们的父节点。
从这两个例子应该很清楚，你不能假设堆中的中位数总是叶节点。