data-structures - 证明最小堆中的最大项必须在其中一个叶子上

Question

我怎样才能证明最小堆中的最大项目必须在一个叶子上，在一个有 N 个项目的树中？

我了解最小堆的整体设计，并且可以显示/图解最大项目位于其中一个叶子（深度 N + 1 的节点> 深度 N 的节点）。我只是不确定我应该如何格式化证明。

Answer 1

首先，请注意“堆”属性要求以非叶节点为根的子树也应该保持堆属性，因为它们也是堆。对于最小堆，“堆”属性是根值应小于子级的值。

如果最小堆的任何非叶节点拥有最大项，则违反以当前非叶节点为根的子树的堆属性，因为该子树的子值小于根值。为了保持堆属性，根值必须向下浮动到其中一个孩子。

为了不违反“堆”属性，“最大值”项的向下浮动将一直持续到持有最大值的节点没有更多子节点为止。因此，“最大”项将始终位于没有子节点的节点（即叶节点）。

Answer 2

为了简单地说明答案，为了矛盾起见，假设最大值在非叶中。这违反了堆属性，对于最小堆，该属性要求节点的值小于其子节点的值。因此，最大值必须在叶子中。