6

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

要素の数を指定して、k番目の要素を（BFSの順序で）見つけるにはどうすればよいですか？O（logn）時間でできると思います。

4

1 に答える 1

15

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

バイナリヒープは完全なバイナリツリー（おそらく最後のレベルを除く）であることがわかっているので、ツリーの形状は、いくつかの高さ（いくつかのkに対して2 kのノードを含む）の完全なバイナリツリーであり、いくつかの数があります。ノードは左から右に入力されます。これらのツリーの本当に気の利いたプロパティは、画像内のノードの数を書き出すときに発生します。値のインデックスを1つ作成します。

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

各レイヤーは、2の累乗のノードで始まることに注意してください。それで、仮に、あなたが数13を調べたいと仮定しましょう。13以下の2の最大の累乗は8であるため、13が行に表示されなければならないことがわかります。

  8  9 10 11 12 13 14 15

これで、この知識を使用して、13からツリーのルートまでのパスをリバースエンジニアリングできます。たとえば、13はこの行の数字の後半にあることがわかります。つまり、13はルートの右側のサブツリーに属します（左側のサブツリーに属している場合は、次のサブツリーに属します）。 8、9、10、および11）これは、ルートから直接移動して、数値の半分を捨てて取得できることを意味します。

12 13 14 15

これで、ツリーのノード3にいます。それで、私たちは左に行くのですか、それとも右に行くのですか？13はこれらの数値の前半にあるので、この時点でノード3の左側のサブツリーに降りる必要があることがわかります。これでノード6に移動し、前半が残ります。番号：

12 13

13はこれらのノードの右半分にあるので、右に降りてノード13に移動する必要があります。があった！

では、このプロセスはどのように機能しましたか？さて、私たちが使用できる本当に、本当にかわいいトリックがあります。上記と同じツリーをバイナリで書きましょう。

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

ノード13の場所を指摘しました。アルゴリズムは次のように機能しました。

  1. ノードを含むレイヤーを見つけます。
  2. 問題のノードにいない間：
    1. ノードがそのレイヤーの前半にある場合は、左に移動して範囲の右半分を破棄します。
    2. ノードがそのレイヤーの後半にある場合は、右に移動して範囲の左半分を破棄します。

これがバイナリで何を意味するかを考えてみましょう。ノードを含むレイヤーを見つけることは、数値に設定されている最上位ビットを見つけることと同じです。バイナリ表現1101を持つ13では、MSBは8ビットです。これは、8から始まるレイヤーにいることを意味します。

では、左側のサブツリーにいるのか、右側のサブツリーにいるのかをどのように判断するのでしょうか。そのためには、このレイヤーの前半にいるのか後半にいるのかを確認する必要があります。そして今、かわいいトリックのために-MSBの後の次のビットを見てください。このビットが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.

元の写真を見ると、これが正しい道です。

このアルゴリズムの大まかなC/C++擬似コードは次のとおりです。

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;
}

私はこのコードをテストしていません！ Don Knuthを言い換えると、概念的には正しいことをしていることを示しました。ここで1つずつエラーが発生する可能性があります。

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

お役に立てれば！

于 2012-12-12T19:36:57.190 に答える