max-min堆中常数时间查找最大最小值的证明困惑与求解

为什么根节点必定是最大值 #

合法的max-min堆（经过正确构建和维护的）核心性质之一是：偶数深度（根为深度0）的节点是其所在整个子树的最大值。根节点的子树就是整个堆，因此根必然是整个堆的最大值。

如果仅从你提到的“偶深度节点≥子节点，奇深度节点≤子节点”的表面规则推导，结合堆的维护逻辑（插入/删除时的调整），可以用反证法理解：
假设存在非根节点X的值大于根R，那么从R到X的路径上，节点深度的奇偶性交替变化：

• R（偶）≥ 子节点V1（奇）
• V1（奇）≤ 子节点V2（偶）
• V2（偶）≥ 子节点V3（奇）
• ...
  最终到X时，若X在偶深度，根据max-min堆的维护规则，X作为偶深度节点（子树最大值）必须和其祖父节点比较，若X比祖父大则交换，直到X的祖先中没有比它小的偶深度节点——这个过程最终会让X上浮到根节点，矛盾；若X在奇深度，它的值必然≤其父节点（偶深度），而父节点又≤根节点，因此X≤根节点，同样矛盾。

综上，合法的max-min堆中根节点一定是最大值。

如何在常数时间内找到最小值 #

同样基于max-min堆的核心性质：奇数深度的节点是其所在整个子树的最小值，即该节点的值≤所有后代节点的值。

由此可以推导：

• 根的直接子节点处于深度1（奇数），它们各自是自己子树的最小值，而这些子树覆盖了除根之外的整个堆。
• 因此，整个堆的最小值只有两种可能：
  • 若堆仅包含根节点，最小值就是根；
  • 否则，最小值是根的所有直接子节点中的最小值。

完全二叉树中，根节点最多只有2个直接子节点——无论堆的规模多大，只需要检查这最多2个节点就能确定最小值，这显然是常数时间操作。

你担心的“遍历所有奇数深度节点”完全没必要，因为更深层的奇数节点的值都≥它们的祖父节点（深度1的节点），不可能比深度1的节点更小。

内容的提问来源于stack exchange，提问作者Rami Mamadov