堆树中的第 K 个元素 [英] K-th element in a heap tree

问题描述

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

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

鉴于其中的元素数量，如何找到第 k 个元素(以 BFS 顺序)?我认为它可以在 O(logn) 时间内完成..

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..

推荐答案

(我假设第 k 个元素(以 BFS 顺序)"是指从上到下的角度的第 k 个元素，从左到右扫描输入.)

(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.)

既然你知道一个二叉堆是一棵完全二叉树(除了最后一层)，你知道这棵树的形状是一棵具有一定高度的完美二叉树(包含 2^k 某些 k) 的节点，从左到右填充一定数量的节点.当你写出图片中节点的数量，对值进行一个索引时，这些树的一个非常漂亮的属性就会出现:

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 2^k 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

请注意，每一层都以一个 2 的幂的节点开始.假设，假设您要查找数字 13.不大于 13 的 2 的最大幂是 8，因此我们知道 13 必须出现在该行中

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

我们现在可以使用这些知识对从 13 返回到树根的路径进行逆向工程.例如，我们知道13在这一行数字的后半部分，这意味着13属于根的右子树(如果它属于左子树，那么我们将在包含8, 9, 10, 和 11.)这意味着我们可以从根开始，扔掉一半的数字得到

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

我们现在位于树中的节点 3.那么我们是向左还是向右?嗯，13 在这些数字的前半部分，所以我们现在知道我们需要下降到节点 3 的左子树.这将我们带到节点 6，现在我们剩下的是前半部分数字:

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 位于这些节点的右半部分，所以我们应该向右下降，将我们带到节点 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
                                 ^^^^

我已经指出了节点 13 的位置.我们的算法按以下方式工作:

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

1. 找到包含节点的层.
2. 虽然不在相关节点上:

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

1. 如果节点位于其所在层的前半部分，则向左移动并丢弃范围的右半部分.
2. 如果节点位于其所在层的后半部分，则向右移动并丢弃范围的左半部分.

让我们想想这在二进制中意味着什么.查找包含节点的层等效于查找数字中设置的最高有效位.在 13 中，二进制表示为 1101，MSB 是 8 位.这意味着我们在从 8 开始的层中.

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.

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

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.

一旦我们这样做了，我们就可以重复这个过程.我们在下一级做什么?好吧，如果下一位是零，我们向左走，如果下一位是 1，我们向右走.看看这对 13 意味着什么:

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.

换句话说，只需查看 MSB 后面的数字位，我们就可以拼出从树的根到我们所讨论的节点的路径！

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!

这总是有效吗！你打赌！让我们试试数字 7.它的二进制表示为 0111.MSB 位于 4 的位置.使用我们的算法，我们会这样做:

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!

以下是该算法的一些粗略的 C/C++ 伪代码:

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

我还没有测试过这段代码！用 Don Knuth 的话说，我刚刚证明了它在概念上做了正确的事情.我这里可能有一个逐一错误.

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.

那么这段代码有多快?好吧，第一个循环会一直运行，直到找到大于 n 的 2 的第一个幂，这需要 O(log n) 时间.循环的下一部分一次向后计数 n 位，在每一步执行 O(1) 工作.因此，整个算法总共需要O(log n) 时间.

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.

希望这有帮助！

这篇关于堆树中的第 K 个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！