tree - 二元最大堆的中位数总是叶节点吗？

Question

如果我有一个二叉最大堆（具有最大堆属性的几乎完整的二叉树），那么中位数是否总是一个叶节点？我找到了一些例子，但还没有找到反例——尽管到目前为止这还不足以让我正式证明这一点。

即对于中位数为 [3] 的值集 {1,2,3,4,5}，树将是：

    5  
   / \
  4   [3]
 / \
2   1

所以在这种情况下，中位数是一个叶节点。

Answer 1

不，它并不总是叶节点。您可以轻松地重新排列您的示例来证明这一点。使用这些相同项目的另一个有效最大堆是：

    5  
   / \
 [3]  4
 / \
2   1

考虑一个包含 7 个项目的完整最大堆：

       7
   6     [4]
 1   5  3   2

这是一个有效的最大堆。最大的项目在根，所有的子节点都小于它们的父节点。

从这两个示例中可以清楚地看出，您不能假设堆中的中位数始终是叶节点。