堆树中的第k个元素

Question

我有一个堆（像二叉树一样实现：每个节点都有两个指向子节点的指针和一个指向父节点的指针）。

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

Answer 1

（我假设“kth元素（以BFS顺序）”是指从输入的从上到下、从左到右扫描的角度来看的第k个元素。）

由于您知道二进制堆是一个完整的二叉树（可能在最后一级除外），所以您知道树的形状是一个具有一定高度的完美二叉树，对于某些k，它包含2^k个节点），从左到右填充了一定数量的节点。当你写出图片中节点的编号时，这些树的一个非常漂亮的属性就出现了，其中一个索引值是：

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

请注意，每一层都从一个2的幂的节点开始。让我们假设，假设，你想查找数字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号节点的位置。我们的算法以如下方式工作:

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的话，我刚刚展示了它在概念上做了正确的事情。我可能在这里犯了一个错误。

   那么这个代码有多快？好吧，第一个循环一直运行，直到找到大于n的二的一次幂，这需要O（logn）时间。循环的下一部分一次倒计数n个位，每一步做O（1）功。因此，整个算法总共需要O（log n）个时间。

   希望这有帮助！