6

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

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

4

1 回答 1

15

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

由于您知道二叉堆是一棵完全二叉树（可能在最后一层除外），因此您知道树的形状是具有一定高度的完美二叉树（对于某些 k，包含 2 k个节点），具有一定数量的节点从左到右填充。当您写出图片中节点的数量时，这些树的一个非常漂亮的属性就会出现，对这些值进行单索引：

                      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. 如果节点位于其所在层的后半部分，则向右移动并丢弃范围的左半部分。

让我们考虑一下这在二进制中意味着什么。找到包含节点的层相当于找到数字中设置的最高有效位。在 13 中，有二进制表示 1101，MSB 是 8 位。这意味着我们处于从 8 开始的层中。

那么我们如何确定我们是在左子树还是右子树呢？好吧，要做到这一点，我们需要看看我们是在这一层的前半部分还是后半部分。现在来看一个可爱的技巧 -看看 MSB 之后的下一位。如果该位设置为 0，则我们处于范围的前半部分，否则我们处于范围的后半部分。因此，我们可以通过查看数字的下一位来确定我们在范围的哪一半！这意味着我们可以通过查看数字的下一位来确定要下降到哪个子树。

一旦我们这样做了，我们就可以重复这个过程。我们在下一个级别做什么？好吧，如果下一位是零，我们向左走，如果下一位是一，我们向右走。看看这对 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 的 2 的第一次幂，这需要 O(log n) 时间。循环的下一部分一次通过 n 的位向后计数，在每一步做 O(1) 工作。因此，整个算法总共需要O(log n) 时间。

希望这可以帮助！

于 2012-12-12T19:36:57.190 回答