ヒープツリーのK番目の要素

Question

私はヒープを持っています（バイナリツリーのように実装されています。各ノードには子へのポインタが2つあり、親へのポインタが1つあります）。

要素の数があれば、どのようにk番目の要素を（BFS順に）見つけることができますか？私はそれがO（logn）時間で実行できると思います。

Answer 1

（私は "kth要素（BFS順）"と仮定しています）は、上から下の観点からk番目の要素を意味しています入力の左から右へのスキャン）

バイナリヒープが完全なバイナリツリー（おそらく最後のレベルを除く）であることを知っているので、ツリーの形は完全なバイナリツリーですいくつかの高さ（いくつかのkでは2 ^kのノードを含みます）があり、いくつかのノードが左から右に埋められています。それぞれの層は、2の累乗だノードから始まること

     1 
      2    3 
     4  5  6  7 
     8 9 10 11 12 13 14 15 

注意：これらの木の本当に気の利いたプロパティは、値を1-インデックス付け、画像内のノードの数を書き出すときに発生します。だから、あなたは数13 13が8を超えない2の最大のパワーを調べたかったこと、のは、仮に、仮定しましょう、私たちは13が

8 9 10 11 12 13 14 15 

我々は今、これを使用することができ、行に表示されなければならないことを知っています13のバック・アップからツリーのルートまでのパスをリバース・エンジニアリングする知識。たとえば、13行目はこの行の数字の後半にあります。つまり、13がルートの右側のサブツリーに属していることを意味します（左側のサブツリーに属していれば、サブツリーに含まれます）。 8、9、10、および11）これは、我々は右ルートから行くと、私たちは、ツリー内のノード3になりました

12 13 14 15 

を取得するために、数字の半分を捨てることができます。私たちは左か右に行くのですか？さて、この数字の最初の半分に13があるので、この時点でノード3の左のサブツリーに降下する必要があることがわかります。これはノード6に移動します。番号：

12 13 

13は、これらのノードの右半分にあるので、我々は13出来上がりノードために私たちを取って、右に降りる必要があります！があった！

このプロセスはどのように機能しましたか？さて、本当にかわいいトリックがあります。私は私達のアルゴリズムは次のように働いていたノード13の位置を指摘してきた

     0001 
      0010     0011 
     0100  0101  0110  0111 
    1000 1001 1010 1011 1100 1101 1110 1111 
           ^^^^ 

：

1. 含む層を探すのは同じ、我々は上記の持っていた木が、バイナリでを書き出してみましょうノード
2. 問題のノードでないが：ノードは、それが中だ層の前半にある場合は、左と範囲の右半分を捨てるに移動
   1. 。
   2. ノードがレイヤーの後半にある場合は、右に移動して範囲の左半分をスローします。

のは、これはバイナリで何を意味するのかについて考えてみましょう。ノードを含むレイヤーを見つけることは、に設定された最上位ビットを見つけることに相当するです。バイナリ表現1101を有する13において、MSBは8ビットである。つまり、レイヤーは8から始まります。

私たちが左のサブツリーか右のサブツリーにいるかはどうやって判断しますか？さて、そうするために、私たちがこの層の前半か後半かを見なければなりません。かわいいトリック - 今すぐMSBの次のビットを見てください。このビットが0に設定されている場合は、範囲の前半にあり、それ以外の場合は後半になります。したがって、我々は数の次のビットを見るだけで、範囲の半分を判断することができます！これは、番号の次のビットだけを見ることで、どのサブツリーに降下するかを判断できることを意味します。

これが完了したら、このプロセスを繰り返すことができます。私たちは次のレベルで何をしますか？さて、次のビットが0の場合は左に移動し、次のビットが1の場合は右に移動します。これは13のために何を意味するのかを見てみましょう：言い換えれば

1101 
    ^^^ 
    ||| 
    ||+--- Go right at the third node. 
    || 
    |+---- Go left at the second node. 
    | 
    +----- Go right at the first node. 

を、私たちはMSBの後に数のビットを調べることで、質問に私たちのノードに、ツリーのルートからのパスを綴ることができます！

これは常に機能しますか？あなたは賭ける！番号7を試してみましょう。これはバイナリ表現0111です。MSBは4の場所にあります。アルゴリズムを使用すると、次のようになります。

0111 
    ^^ 
    || 
    |+--- Go right at the second node. 
    | 
    +---- Go right at the first node. 

私たちの元の画像を見ると、これは正しい道です！私はこのコードをテストしていない

Node* NthNode(Node* root, int n) { 
    /* Find the largest power of two no greater than n. */ 
    int bitIndex = 0; 
    while (true) { 
     /* See if the next power of two is greater than n. */ 
     if (1 << (bitIndex + 1) > n) break; 
     bitIndex++; 
    } 

    /* Back off the bit index by one. We're going to use this to find the 
    * path down. 
    */ 
    bitIndex--; 

    /* Read off the directions to take from the bits of n. */ 
    for (; bitIndex >= 0; bitIndex--) { 
     int mask = (1 << bitIndex); 
     if (n & mask) 
      root = root->right; 
     else 
      root = root->left; 
    } 
    return root; 
} 

：ここ

は、このアルゴリズムのためのいくつかの大まかなC/C++擬似コードです！ドン・クヌースの言い換えに、私は概念的に正しいことを示しています。私はここにひとつずつ誤りがあるかもしれません。

このコードはどのくらい速いのですか？最初のループは、nより大きい2の最初の累乗を見つけるまで実行されます。これはO（log n）時間がかかります。ループの次の部分は、各ステップでO（1）の作業を行いながら、nのビットを1回ずつ後方にカウントします。したがって、全体のアルゴリズムは、O（log n）時間の合計であるをとる。

希望すると便利です。