18

引用维基百科：

使用传统的二叉树数据结构来实现二叉堆是完全可以接受的。添加可以通过算法解决 的元素时，在二进制堆的最后一级找到相邻元素存在问题......

关于这种算法如何工作的任何想法？

我无法找到有关此问题的任何信息，因为大多数二进制堆都是使用数组实现的。

任何帮助表示赞赏。

最近，我注册了一个 OpenID 帐户，无法编辑我的初始帖子，也无法评论答案。这就是为什么我通过这个答案做出回应。非常遗憾。

引用米奇小麦：

@Yse：您的问题是“如何找到二进制堆的最后一个元素”？

是的。或者更准确地说，我的问题是：“如何找到非基于数组的二进制堆的最后一个元素？”。

引用抑制火：

你在问这个问题时有什么背景吗？（即，您是否正在尝试解决一些具体问题？）

如上所述，我想知道一种“找到基于非数组的二进制堆的最后一个元素”的好方法，这是插入和删除节点所必需的。

引用罗伊的话：

对我来说，使用普通的二叉树结构（使用定义为 [data, pLeftChild, pRightChild] 的 pRoot 和 Node）并添加两个额外的指针（pInsertionNode 和 pLastNode）似乎是最容易理解的。pInsertionNode 和 pLastNode 都将在插入和删除子例程期间更新，以在结构中的数据更改时保持它们的最新状态。这使 O(1) 可以访问结构的插入点和最后一个节点。

是的，这应该有效。如果我没记错的话，当它们的位置由于删除/插入而更改为另一个子树时，找到插入节点和最后一个节点可能会有点棘手。但我会试一试。

引用 Zach Scrivena 的话：

如何执行深度优先搜索...

是的，这将是一个很好的方法。我也会试试看。

我仍然想知道，是否有办法“计算”最后一个节点和插入点的位置。具有 N 个节点的二叉堆的高度可以通过取大于 N 的 2 的最小幂的对数（以 2 为底）来计算。也许也可以计算最深层次的节点数。然后有可能确定必须如何遍历堆才能到达插入点或删除节点。

4

6 回答 6

21

基本上，引用的语句是指解决在堆中插入和删除数据元素的位置问题。为了保持二叉堆的“形状属性”，堆的最低层必须始终从左到右填充，不留空节点。为了保持二进制堆的平均 O(1) 插入和删除时间，您必须能够确定下一次插入的位置以及用于删除根节点的最低级别上的最后一个节点的位置，两者在恒定时间内。

对于存储在数组中的二进制堆（其隐式压缩数据结构，如 Wikipedia 条目中所述），这很容易。只需在数组末尾插入最新的数据成员，然后将其“冒泡”到位（遵循堆规则）。或者用数组“冒泡”中的最后一个元素替换根以进行删除。对于数组存储中的堆，堆中元素的数量是一个隐式指针，指向要插入下一个数据元素的位置以及在哪里找到要用于删除的最后一个元素。

对于存储在树结构中的二叉堆来说，这个信息并不那么明显，但是因为它是一棵完整的二叉树，所以可以计算出来。例如，在具有 4 个元素的完全二叉树中，插入点将始终是根节点左孩子的右孩子。用于删除的节点将始终是根节点的左子节点的左子节点。对于任何给定的任意树大小，树将始终具有特定的形状，并具有明确定义的插入和删除点。因为这棵树是一个“完全二叉树”，对于任何给定的大小都具有特定的结构，所以很有可能在 O(1) 时间内计算出插入/删除的位置。然而，问题是即使你知道它在结构上的位置，你也不知道节点在内存中的位置。所以，您必须遍历树才能到达给定的节点，这是一个 O(log n) 过程，使所有插入和删除的最小时间为 O(log n)，从而破坏了通常需要的 O(1) 行为。任何搜索（“深度优先”，或其他一些）也将至少为 O(log n)，因为已注意到遍历问题，并且由于半排序堆的随机性质，通常为 O(n)。

诀窍是能够通过扩充数据结构（“线程化”树，如 Wikipedia 文章中所述）或使用其他指针，在恒定时间内计算和引用这些插入/删除点。

在我看来是最容易理解的实现，具有低内存和额外的编码开销，只是使用普通的简单二叉树结构（使用定义为 [data, pParent, pLeftChild, pRightChild] 的 pRoot 和节点）和添加两个额外的指针（pInsert 和 pLastNode）。pInsert 和 pLastNode 都将在插入和删除子例程期间更新，以在结构中的数据更改时保持它们的最新状态。此实现为结构的插入点和最后一个节点提供了 O(1) 访问权限，并且应该允许在插入和删除中保留整体 O(1) 行为。实现的成本是插入/删除子例程中的两个额外指针和一些额外的小代码（又名，最小）。

编辑：为 O(1) insert() 添加伪代码

这是平均为 O(1) 的插入子例程的伪代码：

define Node = [T data, *pParent, *pLeft, *pRight]

void insert(T data)
{
    do_insertion( data );   // do insertion, update count of data items in tree

    # assume: pInsert points node location of the tree that where insertion just took place
    #   (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)

    int N = this->CountOfDataItems + 1;     # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion

    p = new Node( <null>, null, null, null);        // new empty node for the next insertion

    # update pInsert (three cases to handle)
    if ( int(log2(N)) == log2(N) )
        {# #1 - N is an exact power of two
        # O(log2(N))
        # tree is currently a full complete binary tree ("perfect")
        # ... must start a new lower level
        # traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
        pInsert = pRoot;
        while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; }    # log2(N) iterations
        p->pParent = pInsert;
        pInsert->pLeft = p;
        }
    else if ( isEven(N) )
        {# #2 - N is even (and NOT a power of 2)
        # O(1)
        p->pParent = pInsert->pParent;
        pInsert->pParent->pRight = p;
        }
    else 
        {# #3 - N is odd
        # O(1)
        p->pParent = pInsert->pParent->pParent->pRight;
        pInsert->pParent->pParent->pRight->pLeft = p;
        }
    pInsert = p;

    // update pLastNode
    // ... [similar process]
}

因此，insert(T) 平均为 O(1)：在所有情况下都恰好为 O(1)，除非当树为 O(log N) 时必须将树增加一级，这种情况发生在每 log N 次插入（假设没有删除）。添加另一个指针 (pLeftmostLeaf) 可以使 insert() 在所有情况下都为 O(1) 并避免在完整的完全二叉树中交替插入和删除的可能病理情况。（添加 pLeftmost 留作练习 [这相当容易]。）

于 2009-02-01T07:58:26.823 回答
9

我第一次参加堆栈溢出。

是的，Zach Scrivena 的上述回答（天哪，我不知道如何正确称呼其他人，抱歉）是正确的。如果给定节点数，我想添加的是一种简化的方法。

基本思想是：

给定这棵完整二叉树中的节点数 N，进行“N % 2”计算并将结果压入堆栈。继续计算直到 N == 1。然后将结果弹出。结果是 1 表示右，0 表示左。该序列是从根到目标位置的路线。

例子：

树现在有 10 个节点，我想在位置 11 插入另一个节点。如何路由它？

11 % 2 = 1  --> right    (the quotient is 5, and push right into stack)
 5 % 2 = 1  --> right    (the quotient is 2, and push right into stack)
 2 % 2 = 0  --> left     (the quotient is 1, and push left into stack. End)

然后弹出堆栈：左 -> 右 -> 右。这是从根开始的路径。

于 2016-02-04T04:13:50.013 回答
7

您可以使用二进制堆大小的二进制表示来查找 O(log N) 中最后一个节点的位置。可以存储和增加大小，这将花费 O(1) 时间。这背后的基本概念是二叉树的结构。

假设我们的堆大小是 7。7 的二进制表示是“111”。现在，请记住始终省略第一位。所以，现在我们只剩下“11”了。从左到右阅读。该位为“1”，因此，转到根节点的右子节点。那么左边的字符串是“1”，第一位是“1”。因此，再次转到您所在的当前节点的右子节点。由于您不再有要处理的位，这表明您已到达最后一个节点。因此，该过程的原始工作是将堆的大小转换为位。省略第一位。根据最左边的位，如果为'1'则转到当前节点的右孩子，如果为'0'则转到当前节点的左孩子。

正如你一直到二叉树的最后一样，这个操作总是需要 O(log N) 时间。这是找到最后一个节点的简单而准确的过程。

初读时你可能不明白。尝试在纸上针对二进制堆的不同值使用这种方法，我相信你会得到它背后的直觉。我相信这些知识足以解决你的问题，如果你想用数字解释更多，你可以参考我的博客。

希望我的回答对您有所帮助，如果有，请告诉我...！☺

于 2015-02-08T11:31:42.340 回答
1

如何执行深度优先搜索，在右孩子之前访问左孩子，以确定树的高度。此后，您遇到的第一个具有较短深度的叶子，或者缺少孩子的父节点会在“冒泡”之前指示您应该将新节点放置在哪里。

上面的深度优先搜索 (DFS) 方法并不假设您知道树中的节点总数。如果这些信息可用，那么我们可以利用完全二叉树的特性快速“放大”到所需的位置：

令N为树中的节点总数，H为树的高度。

( N , H ) 的一些值是 (1,0), (2,1), (3,1), (4,2), ..., (7,2), (8, 3)。两者相关的一般公式是H = ceil[log2( N +1)] - 1。现在，仅给定N，我们希望以最少的步数从根遍历到新节点的位置，即没有任何“回溯”。我们首先计算高度为H = ceil[log2( N +1)] - 1的完美二叉树中的节点总数M，即M = 2^( H +1) - 1。

如果N == M，那么我们的树是完美的，新节点应该添加到新的级别。这意味着我们可以简单地执行 DFS（从左到右），直到我们碰到第一个叶子；新节点成为这片叶子的左孩子。故事结局。

但是，如果N < M，那么我们树的最后一层仍有空位，新节点应该添加到最左边的空位。已经在我们树的最后一层的节点数只是 ( N - 2^ H + 1)。这意味着新节点在最后一级从左侧取点X = ( N - 2^ H + 2)。

现在，要从根部到达那里，您需要在每个级别进行正确的转弯（L vs R），以便您最终到达最后一个级别的X点。在实践中，您将在每个级别通过少量计算来确定转弯。但是，我认为下表显示了总体情况和相关模式，而不会陷入算术的困境（您可能会将其视为均匀分布的算术编码形式）：

0 0 0 0 0 X 0 0 <--- represents the last level in our tree, X marks the spot!
          ^
L L L L R R R R <--- at level 0, proceed to the R child
L L R R L L R R <--- at level 1, proceed to the L child
L R L R L R L R <--- at level 2, proceed to the R child 
          ^                      (which is the position of the new node)
          this column tells us
          if we should proceed to the L or R child at each level

编辑：假设我们知道树中的节点总数，添加了关于如何以最短的步骤到达新节点的描述。

于 2009-02-01T05:01:32.343 回答
0

如果您没有参考父母的解决方案！要为下一个节点找到合适的位置，您需要处理 3 个案例

  • 案例（1）树级完整 Log2(N)
  • 案例（2）树节点数为偶数
  • 案例（3）树节点数为奇数

插入：

void Insert(Node root,Node n)
{
Node parent = findRequiredParentToInsertNewNode (root);
if(parent.left == null)
parent.left = n;
else
parent.right = n;
}

找到节点的父节点以插入它

void findRequiredParentToInsertNewNode(Node root){

Node last = findLastNode(root);

 //Case 1 
 if(2*Math.Pow(levelNumber) == NodeCount){
     while(root.left != null)
      root=root.left;
  return root;
 }
 //Case 2
 else if(Even(N)){
   Node n =findParentOfLastNode(root ,findParentOfLastNode(root ,last));
 return n.right;
 }
//Case 3
 else if(Odd(N)){
  Node n =findParentOfLastNode(root ,last);
 return n;
 }

}

要找到最后一个节点，您需要执行 BFS（广度优先搜索）并获取队列中的最后一个元素

 Node findLastNode(Node root)
 {
     if (root.left == nil)
         return root

     Queue q = new Queue();

     q.enqueue(root);
     Node n = null;

     while(!q.isEmpty()){
      n = q.dequeue();
     if ( n.left != null )
         q.enqueue(n.left);
     if ( n.right != null )
         q.enqueue(n.right);
        }
   return n;
}

查找最后一个节点的父节点，以便将节点设置为空，以防在删除情况下替换为根节点

 Node findParentOfLastNode(Node root ,Node lastNode)
{
    if(root == null)
        return root;

    if( root.left == lastNode || root.right == lastNode )
        return root;

    Node n1= findParentOfLastNode(root.left,lastNode);
    Node n2= findParentOfLastNode(root.left,lastNode);

    return n1 != null ? n1 : n2;
}
于 2013-07-31T01:20:58.473 回答
0

我知道这是一个旧线程，但我正在寻找同一个问题的答案。但是我不能做一个 o(log n) 解决方案，因为我必须在几秒钟内找到最后一个节点数千次。我确实有一个 O(log n) 算法，但我的程序正在爬行，因为它执行此操作的次数。所以经过深思熟虑，我终于找到了解决这个问题的方法。不确定是否有人觉得这很有趣。

这个解决方案是 O(1) 的搜索。对于插入，它肯定小于 O(log n)，尽管我不能说它是 O(1)。

只是想补充一点，如果有兴趣，我也可以提供我的解决方案。解决方案是将二进制堆中的节点添加到队列中。每个队列节点都有前后指针。我们不断地从左到右将节点添加到此队列的末尾，直到到达二进制堆中的最后一个节点。此时，二进制堆中的最后一个节点将位于队列的末尾。每次需要找到最后一个节点时，我们从后面出列，现在倒数第二个成为树中的最后一个节点。当我们想要插入时，我们从后面向后搜索我们可以插入的第一个节点并将其放在那里。它不完全是 O(1)，但大大减少了运行时间。

于 2017-11-07T18:18:28.123 回答