二叉堆插入，不理解循环 [英] Binary heap insertion, don't understand for loop
问题描述
在Weiss的数据结构和算法在Java中，他解释道插入算法二叉堆正是如此
In Weiss 'Data Structures and Algorithms In Java", he explains the insert algorithm for binary heaps thusly
public void insert( AnyType x )
{
if( currentSize == array.length -1)
enlargeArray( array.length * 2 + 1);
// Percolate up
int hole = ++currentSize;
for(array[0] = x; x.compareTo( array[ hole / 2 ]) < 0; hole /=2 )
array[ hole ] = array[ hole / 2 ];
array[ hole ] = x;
}
我得到移动孔上树的原则，但我不明白他是怎么用这个语法中的for循环...什么初始化完成它的数组[0] = X; 是什么意思？看来，他改写了根值？这似乎是一个很做作一张code。他在干什么ERE？
I get the principle of moving a hole up the tree, but I don't understand how he's accomplishing it with this syntax in the for loop... What does the initializer array[0] = x; mean? It seems he's overwriting the root value? It seems like a very contrived piece of code. What's he doing ere?
推荐答案
首先，我从马克魏斯和他的电子邮件回复基本上说，code是正确的（在这个答案的底部充分反应）。
First off, I got a response from Mark Weiss and his email basically said the code was correct (full response at the bottom of this answer).
他还表示，这样的：
因此，最小项是在数组索引1所示findMin。做一个插入，你按照从下到根的路径。
Consequently, the minimum item is in array index 1 as shown in findMin. To do an insertion, you follow the path from the bottom to the root.
索引1？嗯...然后我不得不回去，重新阅读大章的部分，当我看到图6.3是点击了。
Index 1? Hmmm... I then had to go back and re-read larger portions of the chapter and when I saw figure 6.3 it clicked.
该数组是基于0的，但被认为是堆的一部分内容是从指数1日起保存。图6.3是这样的：
The array is 0-based, but the elements that are considered part of the heap is stored from index 1 and onwards. Illustration 6.3 looks like this:
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| | A | B | C | D | E | F | G | H | I | J | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
值配售元素0是一个哨兵值，使循环终止。
The placing of the value at element 0 is a sentinel value to make the loop terminate.
因此，上述的树，让我们来看看如何插入功能的工作原理。 ^ h 标记下方的孔。
Thus, with the above tree, let's see how the insert function works. H below marks the hole.
首先，我们把 X 到第0个元素（堆外），并将孔在数组中的下一个可用的元素。
First we place x into the 0th element (outside the heap), and places the hole at the next available element in the array.
H
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| x | A | B | C | D | E | F | G | H | I | J | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
然后，我们泡了（渗透）的孔，从半索引运动中的值，直到我们找到正确的位置来放置 X 。
如果我们看一下图6.5和6.6，我们将实际值放入数组：
If we look at figure 6.5 and 6.6, let's place the actual values into the array:
H/2 H
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 | | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
注意，我们放置14中，值插入，成指数0，但是这是在堆外，我们的标记值，以确保在循环终止
Notice that we placed 14, the value to insert, into index 0, but this is outside the heap, our sentinel value to ensure the loop terminates.
然后我们比较值 X 与在值孔/ 2 ，现在是11/2 = 5，x小于31，所以我们把价值和移动孔：
Then we compare the value x with the value at hole / 2, which now is 11/2 = 5. x is less than 31, so we move the value up and move the hole:
H/2 H <---------------------------
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 31 | 19 | 68 | 65 | 26 | 32 | 31 | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
| ^
+--------- move 31 -----------+
我们再次比较，14是再次小于21（5/2 = 2），所以再次：
We compare again, 14 is again less than 21 (5 / 2 = 2), so once more:
H/2 H <------------
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 21 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
| ^
+-- move 21 ---+
现在，然而，14不超过13（孔/ 2 - > 2/1 = 1）少，所以我们已经找到了正确的位置为 X
Now, however, 14 is not less than 13 (hole / 2 --> 2 / 1 = 1), so we've found the right spot for x:
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
| 14 | 13 | 14 | 16 | 24 | 21 | 19 | 68 | 65 | 26 | 32 | 31 | | |
+----+----+----+----+----+----+----+----+----+----+----+----+----+----+
0 1 2 3 4 5 6 7 8 9 10 11 12 13
^
x
正如你所看到的，如果你看看插图6.6和6.7，这符合预期的行为。
As you can see, if you look at illustrations 6.6 and 6.7, this matches the expected behavior.
因此，尽管code是没有错的，你得到了一个小障碍这也许是书的范围之内。
So while the code isn't wrong, you got one little snag that is perhaps outside of scope of the book.
如果对 X型插入是引用类型，你会在当前堆有2个引用刚插入相同的对象。如果然后立即从堆中，它看起来删除对象（但看看那里的看起来像的把我们摆在首位......）之类的第0个元素仍将保留提及，禁止垃圾收集器从做其工作。
If the type of x being inserted is a reference type, you will in the current heap have 2 references to the same object just inserted. If you then immediately delete the object from the heap, it looks (but look where looking like got us in the first place...) like the 0th element will still retain the reference, prohibiting the garbage collector from doing its job.
要确保这里没有隐藏的议程，这里是马克的完整的答案：
To make sure there's no hidden agenda here, here is the complete answer from Mark:
拉塞
在code是正确的。
二进制堆是完全二叉树中，从一个任意路径 底部的根，值永远不会增加。因此最低 项目位于根。再presentation在阵列中，将根 指标1，并在索引i的任一节点，父为I / 2（四舍五入 下）（左孩子是2i和右孩子在2I + 1，但 这里没有必要）。
The binary heap is a complete binary tree in which on any path from a bottom to the root, values never increase. Consequently the minimum item is at the root. The array representation places the root at index 1, and for any node at index i, the parent is at i/2 (rounded down) (the left child is at 2i and the right child at 2i+1, but that is not needed here).
因此，最小项是在数组索引1所示 findMin。做一个插入，你跟着从底部的路径 根。
Consequently, the minimum item is in array index 1 as shown in findMin. To do an insertion, you follow the path from the bottom to the root.
在for循环：
孔/ = 2 EX presses移动孔父的念头。
hole /= 2 expresses the idea of moving the hole to the parent.
则x.compareTo（阵列[孔/ 2]）＆LT; 0 EX presses我们留在这个想法 环路只要x是比母体更小。
x.compareTo( array[ hole / 2 ]) < 0 expresses the idea that we stay in the loop as long as x is smaller than the parent.
现在的问题是，如果x是一个新的最小值，你永远走不出的 安全回路（技术上你崩溃试图比较x和阵列[0]）。 你可以把一个额外的测试来处理边界情况。 另外，在code获取解决，通过加入的X阵列[0]在 一开始，而且由于节点的父母我是I / 2，父的 这是在指数1根可以在索引0找到这可以保证 循环终止，如果x是新的最小（和然后场所x，它 是新的最低根索引1）。
The problem is that if x is a new minimum, you never get out of the loop safely (technically you crash trying to compare x and array[0]). You could put in an extra test to handle the corner case. Alternatively, the code gets around that by putting x in array[0] at the start, and since the "parent" of node i is i/2, the "parent" of the root which is in index 1 can be found in index 0. This guarantees the loop terminates if x is the new minimum (and then places x, which is the new minimum in the root at index 1).
一个较长的解释是在这本书......但这里的基础概念是 即使用定点（或无效）值，以避免额外的$ C $下 边界情况。
A longer explanation is in the book... but the basic concept here is that of using a sentinel (or dummy) value to avoid extra code for boundary cases.
问候，
标记魏斯
这篇关于二叉堆插入，不理解循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
