data-structures - 最小ヒープ内の最大アイテムがリーフの 1 つになければならないことを証明する

Question

最小ヒープ内の最大アイテムが N 個のアイテムを持つツリーの葉の 1 つになければならないことを証明するにはどうすればよいですか?

最小ヒープの全体的な設計を理解しており、最大アイテムがリーフの 1 つにあることを示す/図を描くことができます (深さ N + 1 のノード > 深さ N のノード)。証明をどのようにフォーマットすればよいかわかりません。

Answer 1

まず、「ヒープ」プロパティでは、葉以外のノードをルートとするサブツリーもヒープ プロパティを維持する必要があることに注意してください。min-heap の場合、「ヒープ」プロパティは、ルート値が子の値よりも小さくなければならないということです。

最小ヒープのいずれかの非リーフ ノードが最大項目を保持している場合、このサブツリーの子の値がルート値より小さいため、ルートが現在の非リーフ ノードであるサブツリーのヒープ プロパティに違反します。ヒープ プロパティを維持するには、ルート値を子の 1 つに浮動させる必要があります。

「ヒープ」プロパティに違反しないようにするために、最大値を保持するノードに子がなくなるまで、「最大」アイテムのフローティング ダウンが続行されます。したがって、「最大」項目は常に、子を持たないノード (リーフ ノード) にあります。

Answer 2

答えを簡単に言うと、矛盾を避けるために最大値が非リーフにあると仮定します。これは、最小ヒープの場合、ノードの値がその子よりも小さいことを要求するヒープ プロパティに違反します。したがって、最大値はリーフにある必要があります。