查找二进制堆的最后一个元素

Question

引用维基百科:

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

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

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

任何帮助赞赏.

---

最近,我注册了一个OpenID帐户,无法编辑我的初始帖子或评论答案.这就是我通过这个答案回应的原因.非常遗憾.

---

引用米奇小麦:

@Yse:你的问题是"如何找到二进制堆的最后一个元素"？

是的.或者更确切地说,我的问题是:"我如何找到非基于数组的二进制堆的最后一个元素？".

引用Suppressingfire:

你有没有提出这个问题的背景？(也就是说,你试图解决一些具体问题吗？)

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

引用罗伊:

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

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

引用Zach Scrivena:

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

是的,这将是一个很好的方法.我也会尝试一下.

我还在想,如果有办法"计算"最后一个节点和插入点的位置.具有N个节点的二进制堆的高度可以通过获取大于N的最小二次幂的log(基数2)来计算.也许可以计算最深级别上的节点数.然后可能确定如何遍历堆以到达插入点或节点以进行删除.

Answer 1

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

对于存储在数组中的二进制堆(具有隐含的,压缩的数据结构,如Wikipedia条目中所述),这很容易.只需在数组末尾插入最新的数据成员,然后将其"冒泡"到位(遵循堆规则).或者将数组中的最后一个元素替换为"bubbling down"以进行删除.对于数组存储中的堆,堆中的元素数是一个隐式指针,指向要插入下一个数据元素的位置以及在何处查找要用于删除的最后一个元素.

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

诀窍是能够通过增加数据结构(在维基百科文章中提到"穿线"树)或使用其他指针来在恒定时间内计算和引用那些插入/删除点.

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

编辑:为O(1)插入添加伪代码()

这是插入子例程的伪代码,平均为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是一个练习[很容易].)

Answer 2

我第一次参加堆栈溢出.

是的,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)

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

Answer 3

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

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

由于您始终到二叉树的最后,此操作始终需要O(log N)时间.这是查找最后一个节点的简单而准确的过程.

你可能在一读时不理解它.尝试在纸上使用这种方法来获得二元堆的不同值,我相信你会得到它背后的直觉.我相信这些知识足以解决您的问题,如果您想要更多的数字解释,您可以参考我的博客.

希望我的回答对你有所帮助,如果有,请告诉我......!☺

Answer 4

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

上述深度优先搜索 (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 与 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

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