min-heapで2番目に大きいキーの範囲

Question

min-heap配列の中で2番目に大きな要素を見つける必要があります。

私はそれが木の葉の1つまたは葉の親の1つかもしれないことに気付きました。私は、これらのノードの範囲が - [floor（n/4）+ 1、n]であると結論付けました。 しかし、まだ私はこの公式と一致しないいくつかの木を作ることができます。

ありがとうございました！

Answer 1

私のコメントでは、ヒープに重複したアイテムが存在する可能性があることを考慮していませんでした。重複した項目が可能な場合は、最後のノードを除き、2番目に大きいノードはのノードにすることができます。

重複した項目がない場合、次に大きなノードはリーフレベルにあるか、リーフレベルのすぐ上のレベルにあるノードであり、最大でも1つの子を持ちます。それは子供がいない可能性があります。

の最初のノードは、の次のものが2^(h-2) + 1で、hはツリーの高さです。したがって、このヒープ与えられ、0の高さを有する慣例により、唯一のルートノードを持つツリーは：ツリーは2の高さを有する

 0 
    / \ 
    1  2 
/\ /\ 
    3 4 5 6 

二番目に大きいかもしれない最初のノードが2^(2-2)+1であるか、または

最後の2番目の値を含む可能性のあるノードの範囲は、[2^(h-2) + 1, n-1]です。

上記は、ヒープのルートが配列のインデックス0にあると仮定しています。ルートがインデックス1にある場合、それに応じて調整する必要があります。