0

在 Weiss 的“Java 中的数据结构和算法”中，他解释了二进制堆的插入算法

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 循环中使用这种语法来完成它的......初始化程序array[0] = x;是什么意思？看来他正在覆盖根值？这似乎是一段非常人为的代码。他在这儿做什么？

4

2 回答 2

1

首先，我收到了 Mark Weiss 的回复，他的电子邮件基本上说代码是正确的（完整回复在这个答案的底部）。

他还这样说：

因此，最小项位于数组索引 1 中，如 findMin 所示。要进行插入，请遵循从底部到根的路径。

索引 1？嗯...然后我不得不返回并重新阅读本章的大部分内容，当我看到图 6.3 时，它点击了。

该数组是从 0 开始的，但被认为是堆的一部分的元素从索引 1 开始存储。图 6.3 如下所示：

+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
|   | 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 是使循环终止的标记值。

因此，通过上面的树，让我们看看插入函数是如何工作的。H下面标记了这个洞。

首先，我们x放入第 0 个元素（堆外），并将孔放置在数组中的下一个可用元素处。

                                              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，让我们将实际值放入数组中：

                           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 中，但这在堆之外，这是我们确保循环终止的标记值。

然后我们将该值x与 处的值进行比较hole / 2，现在是 11/2 = 5。x 小于 31，因此我们将值向上移动并移动孔：

            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)，所以再一次：

       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 (hole / 2 --> 2 / 1 = 1)，所以我们找到了正确的位置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，这符合预期的行为。

因此，虽然代码没有错，但您遇到了一个可能超出本书范围的小问题。

如果x被插入的类型是引用类型，您将在当前堆中对刚刚插入的同一个对象有 2 个引用。如果您随后立即从堆中删除该对象，它看起来（但看起来首先让我们看到了......）第 0 个元素仍将保留引用，从而禁止垃圾收集器完成其工作。

为了确保这里没有隐藏的议程，这是马克的完整答案：

嗨，拉斯，

代码是正确的。

二叉堆是一棵完全二叉树，其中在从底部到根的任何路径上，值都不会增加。因此，最小项目位于根部。数组表示将根放在索引 1 处，对于索引 i 处的任何节点，父节点位于 i/2（向下舍入）（左孩子位于 2i，右孩子位于 2i+1，但这不是必需的这里）。

因此，最小项位于数组索引 1 中，如 findMin 所示。要进行插入，请遵循从底部到根的路径。

在 for 循环中：

hole /= 2 表示将孔移动到父级的想法。

x.compareTo(array[hole / 2]) < 0 表示只要 x 小于父级，我们就会留在循环中。

问题是，如果 x 是一个新的最小值，您将永远无法安全地退出循环（从技术上讲，您在尝试比较 x 和 array[0] 时会崩溃）。您可以进行额外的测试来处理角落案例。或者，代码通过在开始时将 x 放入数组 [0] 来解决此问题，并且由于节点 i 的“父”是 i/2，因此可以在索引中找到位于索引 1 中的根的“父” 0. 这保证了如果 x 是新的最小值，则循环终止（然后将 x 放置在索引 1 处的根中，这是新的最小值）。

书中有更长的解释......但这里的基本概念是使用哨兵（或虚拟）值来避免边界情况的额外代码。

问候，

马克·韦斯

于 2014-11-06T08:04:15.083 回答
0

数组初始化程序看起来不对。如果它是array[hole] = x;，那么整个事情就很有意义了。

它首先将值放在树的最低等级（当前大小之后的条目），然后通过查看 (int)hole/2 来查看“上面”的条目。

它一直向上移动，直到比较器告诉它停止。我认为这是对 for 循环语法的轻微误用，因为它感觉真的是一个 while(x.compare(hole/2) < 0) 类型的循环。

于 2014-11-05T14:03:04.787 回答