二进制最大堆的中位数总是叶节点吗？

Question

如果我有一个二进制的max-heap (具有max-heap属性的几乎完全的二叉树)，那么中位数总是叶节点吗？我已经找到了一些例子，但还没有找到反例--尽管到目前为止，这还不足以让我正式证明这一点。

即，对于中位数为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

这是一个有效的max-heap。最大的项在根，并且所有的子节点都比它们的父节点小。

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