找到一个二元堆的最后一个元素 [英] Finding last element of a binary heap

问题描述

引用维基百科：的

这是完全可以接受的使用   传统的二进制树数据结构   为实现二进制数堆。有   一个问题，寻找相邻   就在最后一个级别的元素   添加元素时，二叉堆   它可以是的解决的   *算法* ...

It is perfectly acceptable to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element which can be resolved *algorithmically*...

如何这样的算法可能会奏效任何想法？

Any ideas on how such an algorithm might work?

我没能找到有关此问题的任何信息，对于大多数二进制堆使用数组实现的。

I was not able to find any information about this issue, for most binary heaps are implemented using arrays.

任何帮助AP preciated。

Any help appreciated.

最近，我已经注册了一个OpenID帐户，我不能够编辑我最初的职位，也没有发表评论的答案。这就是为什么我通过这个答案响应。抱歉。

Recently, I have registered an OpenID account and am not able to edit my initial post nor comment answers. That's why I am responding via this answer. Sorry for this.

引用米奇小麦：的

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

@Yse: is your question "How do I find the last element of a binary heap"?

是的，确实如此。 或者更precise，我的问题是：？如何找到的最后一个元素的非基于阵列的的二元堆

Yes, it is. Or to be more precise, my question is: "How do I find the last element of a non-array-based binary heap?".

引用燮pressingfire：的

有一些情况下在其中您   问这个问题？ （即，是否有   你想一些具体的问题   解决？）

Is there some context in which you're asking this question? (i.e., is there some concrete problem you're trying to solve?)

如上所述，我想知道的好方法找到一个非基于阵列的二叉堆的最后一个元素，这是必要的节点插入和删除。

As stated above, I would like to know a good way to "find the last element of a non-array-based binary heap" which is necessary for insertion and deletion of nodes.

引用罗伊：的

这似乎是最理解我往   只需使用普通的二叉树   结构（使用PROOT和节点   定义为数据，pLeftChild，   pRightChild]），并增加两个附加   指针（pInsertionNode和   pLastNode）。 pInsertionNode和   pLastNode都将在更新   插入和删除子程序   让他们当前的数据时，   内部结构的变化。本   给O（1）访问这两个插入   点和结构的最后一个节点

It seems most understandable to me to just use a normal binary tree structure (using a pRoot and Node defined as [data, pLeftChild, pRightChild]) and add two additional pointers (pInsertionNode and pLastNode). pInsertionNode and pLastNode will both be updated during the insertion and deletion subroutines to keep them current when the data within the structure changes. This gives O(1) access to both insertion point and last node of the structure.

是的，这应该工作。如果我没有记错的话，它可能是一个有点棘手找到插入节点和最后一个节点，当其位置改变到另一个子树由于一个插入/缺失。但我会试试这个。

Yes, this should work. If I am not mistaken, it could be a little bit tricky to find the insertion node and the last node, when their locations change to another subtree due to an deletion/insertion. But I'll give this a try.

引用扎克Scrivena：的

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

How about performing a depth-first search...

是的，这将是一个不错的办法。我会尝试了这一点，太。

Yes, this would be a good approach. I'll try that out, too.

不过我想知道，如果有一种方法来计算的最后一个节点，将插入点的位置。二元堆有N个节点的高度可以通过取2的最小功率是大于N.也许是可能计算上最深层次的节点的数目（基数为2的）对数来计算，也。然后，它是也许可能确定如何堆已被遍历以达到插入点或删除节点

Still I am wondering, if there is a way to "calculate" the locations of the last node and the insertion point. The height of a binary heap with N nodes can be calculated by taking the log (of base 2) of the smallest power of two that is larger than N. Perhaps it is possible to calculate the number of nodes on the deepest level, too. Then it was maybe possible to determine how the heap has to be traversed to reach the insertion point or the node for deletion.

推荐答案

基本上，所引述的语句引用解析为插入和删除的数据元素的位置进入，并从堆的问题。为了保持一个二进制堆的形状属性，堆的最低级别必须充满从左至右留下没有空的节点。维持平均O（1）的插入和删除时间二进制堆时，必须能够确定要用于删除根节点的下一个插入的位置和在最低级别的最后节点的位置，这两个在一定的时间。

Basically, the statement quoted refers to the problem of resolving the location for insertion and deletion of data elements into and from the heap. In order to maintain "the shape property" of a binary heap, the lowest level of the heap must always be filled from left to right leaving no empty nodes. To maintain the average O(1) insertion and deletion times for the binary heap, you must be able to determine the location for the next insertion and the location of the last node on the lowest level to use for deletion of the root node, both in constant time.

有关存储在数组中（其隐含的，简缩式数据结构如Wikipedia条目解释）二元堆，这是很容易。只需插入在数组的末尾最新的数据成员，然后泡沫入到位（以下堆规则）。或使用阵列冒泡下降的缺失，在最后一个元素替换根。为在阵列存储堆，在堆元件的数目是一个隐含的指针到下一个数据元素将被插入并在哪里可以找到用于删除最后一个元素

For a binary heap stored in an array (with its implicit, compacted data structure as explained in the Wikipedia entry), this is easy. Just insert the newest data member at the end of the array and then "bubble" it into position (following the heap rules). Or replace the root with the last element in the array "bubbling down" for deletions. For heaps in array storage, the number of elements in the heap is an implicit pointer to where the next data element is to be inserted and where to find the last element to use for deletion.

有关存储在树结构中的二进制堆，该信息并不明显，但是因为它是一个完整的二进制树，它可以被计算。例如，在与4个元素的完整二进制树中，插入点永远是根节点的左子的右子。节点使用为删除总是根节点的左子的左子。而且任何给定的任意树的大小，树永远有一个特定的形状，具有明确的插入和删除点。因为树是一个完整二进制树的任何给定尺寸为特定的结构，这是非常可能计算插入/缺失的位置在O（1）时间。然而，美中不足的是，即使你知道它在结构上，你不知道的节点会在内存中。所以，你必须遍历树来获得给定的节点，该节点是一个O（log n）的过程中让所有的插入和删除最小O（log n）的，打破了通常所需的O（1）行为。任何搜索（深度优先或其他）将因为遍历问题至少O（log n）的同时指出，通常为O（n）因为半分类堆的随机性。

For a binary heap stored in a tree structure, this information is not as obvious, but because it's a complete binary tree, it can be calculated. For example, in a complete binary tree with 4 elements, the point of insertion will always be the right child of the left child of the root node. The node to use for deletion will always be the left child of the left child of the root node. And for any given arbitrary tree size, the tree will always have a specific shape with well defined insertion and deletion points. Because the tree is a "complete binary tree" with a specific structure for any given size, it is very possible to calculate the location of insertion/deletion in O(1) time. However, the catch is that even when you know where it is structurally, you have no idea where the node will be in memory. So, you have to traverse the tree to get to the given node which is an O(log n) process making all inserts and deletions a minimum of O(log n), breaking the usually desired O(1) behavior. Any search ("depth-first", or some other) will be at least O(log n) as well because of the traversal issue noted and usually O(n) because of the random nature of the semi-sorted heap.

关键是要能够两者的计算和引用的在固定时间内的插入/缺失点或者通过增加的数据结构（线程的树，如提到维基百科文章），或使用额外的指针。

The trick is to be able to both calculate and reference those insertion/deletion points in constant time either by augmenting the data structure ("threading" the tree, as mention in the Wikipedia article) or using additional pointers.

这似乎是我的实现是最容易理解的，低内存和额外的编码开销，是只使用普通的简单的二进制树状结构（使用定义为数据，pParent，pLeftChild，pRightChild一个PROOT和节点]），并增加两个指针（pInsert和pLastNode）。 pInsert和pLastNode都将在插入和删除子程序更新以保持其时效时，内部的结构发生变化的数据。此实现提供了O（1）访问结构既插入点和最后一个节点，并应允许总O（1）行为preservation两个插入和缺失。实施的成本是两个额外的指针和一些小的额外的code。在插入/缺失子程序（即，最小）。

The implementation which seems to me to be the easiest to understand, with low memory and extra coding overhead, is to just use a normal simple binary tree structure (using a pRoot and Node defined as [data, pParent, pLeftChild, pRightChild]) and add two additional pointers (pInsert and pLastNode). pInsert and pLastNode will both be updated during the insertion and deletion subroutines to keep them current when the data within the structure changes. This implementation gives O(1) access to both insertion point and last node of the structure and should allow preservation of overall O(1) behavior in both insertion and deletions. The cost of the implementation is two extra pointers and some minor extra code in the insertion/deletion subroutines (aka, minimal).

修改：加入的伪code为O（1）插入（）

EDIT: added pseudocode for an O(1) insert()

下面是伪code为插入子程序是O（1），平均：

Here is pseudo code for an insert subroutine which is O(1), on average:

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

所以，插入（T）是O（1）平均：完全O（1）除了当树必须增加一个级别时，它是在一切情况下（日志N），这恰好每个日志N插入（假设没有删除）。添加另一个指针（pLeftmostLeaf）可以使插入（）O（1）适用于所有情况，避免交替插入与放大器的可能的病理情况;在删除一个完整的完全二叉树。 （添加pLeftmost留作练习[这是相当容易的。）

So, insert(T) is O(1) on average: exactly O(1) in all cases except when the tree must be increased by one level when it is O(log N), which happens every log N insertions (assuming no deletions). The addition of another pointer (pLeftmostLeaf) could make insert() O(1) for all cases and avoids the possible pathologic case of alternating insertion & deletion in a full complete binary tree. (Adding pLeftmost is left as an exercise [it's fairly easy].)

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