3

1からn個の異なる要素の最大ヒープで3番目に小さい要素の可能なインデックスを見つけるにはどうすればよいですか？私は、最小の要素が葉のどこにでもあることを知っています。2番目に小さいものはnが3より大きい場合はn/2からnの範囲になりますが、3番目に小さいものを計算する方法がわかりません。助言がありますか？

4

1 に答える 1

1

3番目に小さい要素には、最大で2つの子孫があります。これは、その子が葉であるか、葉であることを意味します。（これを証明するには、子が1つしかない要素が子として非リーフを持つことは不可能であることも証明する必要があります。簡単ですが面倒です。）

お気づきのように、葉には範囲内のインデックスがあります[floor(n/2)+1, n]。n/2が整数の場合、その要素には子（リーフ）が1つだけあるため、これを追加すると、2番目に大きい要素を含む可能性のあるインデックスの範囲が得られます。

最初の子が葉の範囲にある要素に[floor(n/2)+1,n]は、最大で2つの子があり、非葉の子はありません。その範囲は[ceil（n / 2）、n]範囲に隣接しており、2つの範囲の和集合は、3番目に大きい要素のすべての可能な位置を提供します。

の要素の最初の子iはインデックスを持っている2iので、最初の子が少なくともである最初の要素floor(n/2)+1はですfloor(n/4)+1。

したがって、3番目に大きい要素を見つけることができる可能性のあるインデックスは、次の範囲です[floor(n/4)+1,n]。

別のアプローチがあります。インデックスでいくつかの要素を取りますi。その直接の子はと2iです2i+1。その孫は4i, 4i+1, 4i+2, 4i+3であり、一般的に、それはレベルの子孫kです; 要約すると、。もちろん、これらの範囲は重複していません（実際、重複していない限り、連続していません）。したがって、レベルに少なくとも1つの子孫がある場合は、すべての子孫の完全なセットもあり、その中にはがあります。2ki, 2ki+1, ..., 2ki + 2ki-1[2ki, ..., 2k(i+1)-1 ]i1ikk' < k2k-2

そのすべてから、次のように結論付けることができます。

  • の場合、次のようになります。n ≥ 2ki and n < 2k(i+1)i

    • 2ki-2あるレベル未満の子孫k

    • n - 2ki+1レベルの子孫k;

    • 合計：n-1子孫。

  • の場合、次のようになります。n ≥ 2k(i+1) and n < 2k+1ii

    • まさに子孫。2k+1-1

大まかに言えば、これは、ヒープの基になる配列の最初の部分に最後の要素が見つからないことを意味します。2k1/2k

于 2013-03-10T03:17:40.600 に答える