堆树中的第K个元素

Question

我有一个堆(像二叉树一样实现:每个节点有两个指向子节点的指针和一个指向父节点的指针).

如果给定元素的数量,我如何找到第k个元素(以BFS顺序)？我认为它可以在O(logn)时间完成..

Answer 1

(我假设通过"第k个元素(以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,则我们处于范围的前半部分,否则我们处于范围的后半部分.因此,我们只需查看数字的下一位即可确定我们所在范围的哪一半!这意味着我们可以通过查看数字的下一位来确定要进入哪个子树.

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

希望这可以帮助!