我有一个堆。（像一个二叉树实现：每个节点具有两个指针给孩子，一个指针到母体）

我如何找到第k个元素（在BFS顺序），鉴于它的元素个数？我认为它可以在O（LOGN）的时间内完成。

解决方案

（我假设k个元素（在BFS顺序）你指从高端到低端的角度第k个元素，左到右的输入的扫描。）

既然你知道，一个二叉堆是完全二叉树（除了可能在最后一个级别），你知道这棵树的形状是一些高度（含2 K 与节点从左至右填充在一定数目的一些k个节点）。当你写出来的节点数的画面发生这些树的一个真正漂亮的财产，一分度值：

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

请注意，每个层开始于一个节点这是二的幂。因此，让我们假设，假设，你想要查找的13号两个最大功率不超过13 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.我们的算法以下面的方式工作的位置：

找到包含节点层。 虽然不是在所讨论的节点： 如果该节点是在第一个它在该层的一半，左右移动，扔掉范围的右半部分。 如果该节点是它在该层的下半年，向右移动，扔掉范围的左半部分。

让我们来想想这意味着什么二进制。查找包含该节点的层是相当于寻找最显著位在数设置即可。 13，其中有二重presentation 1101，最高位为8位。这意味着，我们是在层开始与八。

那么，我们如何确定我们是否是在左子树或右子树？好了，要做到这一点，我们需要看到，如果我们在这第一层或下半年的一半。而现在一个可爱的把戏 - 看后MSB 下位。如果该位被设置为0，我们是在第一范围的一半，否则我们是在范围内的下半年。因此，我们可以判断我们在其中一半的范围内通过看数字的下一位！这意味着我们可以判断通过观察刚在号码下位下降到其中子树

一旦我们做到了这一点，我们就可以重复这一过程。什么是我们的一个新的水平呢？好吧，如果下一位是零，我们向左走，如果下一位是一个，我们去的权利。看看这是什么意思13：

  1101
  ^ ^ ^
  |||
  || + ---向右走，在第三个节点。
  ||
  | + ----转到留在第二个节点。
  |
  + -----向右走，在第一个节点。
 

在换句话说，我们可以拼出从树到我们所讨论节点的根路径只是通过看MSB后的数字的位数！

这是否总是工作！你打赌！让我们尝试了7号这有二重presentation 0111，最高位是4的位置。使用我们的算法，我们应该这样做：

  0111
  ^^
  ||
  | + ---向右走，在第二个节点。
  |
  + ----向右走，在第一个节点。
 

在看我们的原始照片，这是正确的道路，走！

下面是一些粗糙的C / C ++伪code这个算法：

 节点* NthNode（节点*根，INT N）{
    / *找到两个最大功率不大于n。 * /
    INT bitIndex处= 0;
    而（真）{
        / *看看两人的下一个动力大于n。 * /
        如果（1＆其中;≤（bitIndex处+ 1）将N）中断;
        ++ bitIndex处;
    }

    / *后退一个位索引。我们将用它来查找
     *路径下。
     * /
    bitIndex--;

    / *读出方向取从n的比特。 * /
    为（;＆bitIndex处GT; = 0; bitIndex--）{
        INT掩模=（1＆其中;＆所述; bitIndex处）;
        如果（N＆安培;面罩）
            根=根 - ＆GT;权利;
        其他
            根=根 - ＆GT;左;
    }
    返回根;
}
 

我没有测试过！套​​用唐Knuth的，我只是显示这个code，在概念上它做正确的事。我会在这里有一个关情况的一个错误。

因此​​，如何快速是这样的code？好了，第一个循环运行，直到它找到两个第一功率大于n，这需要O（log n）的时间。在循环的下一部分向后计数至n之一的位的时间，这样做的O（1）工作在每一步。总的算法，这样总共需要的 O（log n）的时间

希望这有助于！

I have a heap (implemented like a binary tree: each node has two pointers to the children and one pointer to the parent).

How can I find the k-th element (in a BFS order), given the number of elements in it? I think it can be done in O(logn) time..

解决方案

(I'm assuming by "kth element (in a BFS order)" that you mean the kth element from the perspective of a top-to-bottom, left-to-right scan of the input.)

Since you know that a binary heap is a complete binary tree (except possibly at the last level), you know that the shape of the tree is a perfect binary tree of some height (containing 2k nodes for some k) with some number of nodes filled in from the left to the right. A really nifty property of these trees occurs when you write out the numbers of the nodes in a picture, one-indexing the values:

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

Notice that each layer starts with a node that's a power of two. So let's suppose, hypothetically, that you wanted to look up the number 13. The biggest power of two no greater than 13 is 8, so we know that 13 must appear in the row

  8  9 10 11 12 13 14 15

We can now use this knowledge to reverse-engineer the path from 13 back up to the root of the tree. We know, for example, that 13 is in the latter half of the the numbers in this row, which means that 13 belongs to the right subtree of the root (if it belonged to the left subtree, then we would be in the subtree containing 8, 9, 10, and 11.) This means that we can go right from the root and throw out half of the numbers to get

12 13 14 15

We are now at node 3 in the tree. So do we go left or right? Well, 13 is in the first half of these numbers, so we know at this point that we need to descend into the left subtree of node 3. This takes us to node 6, and now we're left with the first half of the numbers:

12 13

13 is in the right half of these nodes, so we should descend to the right, taking us to node 13. And voila! We're there!

So how did this process work? Well, there's a really, really cute trick we can use. Let's write out the same tree we had above, but in binary:

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

I've pointed out the location of node 13. Our algorithm worked in the following way:

Find the layer containing the node. While not at the node in question:

If the node is in the first half of the layer it's in, move left and throw away the right half of the range. If the node is in the second half of the layer it's in, move right and throw away the left half of the range.

Let's think about what this means in binary. Finding the layer containing the node is equivalent to finding the most significant bit set in the number. In 13, which has binary representation 1101, the MSB is the 8 bit. This means that we're in the layer starting with eight.

So how do we determine whether we're in the left subtree or the right subtree? Well, to do that, we'd need to see if we are in the first half of this layer or the second half. And now for a cute trick - look at the next bit after the MSB. If this bit is set to 0, we're in the first half of the range, and otherwise we're in the second half of the range. Thus we can determine which half of the range we're in by just looking at the next bit of the number! This means we can determine which subtree to descend into by looking just at the next bit of the number.

Once we've done that, we can just repeat this process. What do we do at the next level? Well, if the next bit is a zero, we go left, and if the next bit is a one, we go right. Take a look at what this means for 13:

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

In other words, we can spell out the path from the root of the tree to our node in question just by looking at the bits of the number after the MSB!

Does this always work! You bet! Let's try the number 7. This has binary representation 0111. The MSB is in the 4's place. Using our algorithm, we'd do this:

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

Looking in our original picture, this is the right path to take!

Here's some rough C/C++ pseudocode for this algorithm:

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

I haven't tested this code! To paraphrase Don Knuth, I've just shown that conceptually it does the right thing. I might have an off-by-one error in here.

So how fast is this code? Well, the first loop runs until it finds the first power of two greater than n, which takes O(log n) time. The next part of the loop counts backwards through the bits of n one at a time, doing O(1) work at each step. The overall algorithm thus takes a total of O(log n) time.

Hope this helps!