在A*寻路中使用二叉堆

核心提示： 我们来看如何把一个F值为17的元素添加到已经存在的堆中，我们的堆里现在有7个元素，在A*寻路中使用二叉堆(4)，新元素将被添加到第8个位置，这就是堆看起来的样子，和2*2 + 1 = 5的位置上，它不比任何一个子节点低，新元素被加了下划线，10 30 20 34 38 30 24 17接下

我们来看如何把一个F值为17的元素添加到已经存在的堆中。我们的堆里现在有7个元素，新元素将被添加到第8个位置。这就是堆看起来的样子，新元素被加了下划线。10 30 20 34 38 30 24 17

接下来我们比较它和它的父节点，在 8/2 也就是 4的位置上。位置4当前元素的F值是34。既然17比34低，我们交换两元素的位置。现在我们的堆看起来是这样的:

10 30 20 17 38 30 24 34

然后我们把它和新的父节点比较。因为我们在位置4，我们就把它和 4/2 = 2 这个位置上的元素比较。那个元素的F值是30。因为17比30低，我们再次交换，现在堆看起来是这样的：

10 17 20 30 38 30 24 34

接着我们比较它和新的父节点。现在我们在第二个位置，我们把它和 2/2 = 1，也就是堆顶端的比较。这次，17不比10更低，我们停止，堆保持成现在的样子。

从堆中删除元素

从堆中删除元素是个类似的过程，但是差不多是反过来的。首先，我们删除位置1的元素，现在它空了。然后，我们取堆的最后一个元素，移动到位置1。在堆中，这是结束的条件。以前的末元素被加了下划线。

34 17 20 30 38 30 24

然后我们比较它和两个子节点，它们分别在位置(当前位置*2)和(当前位置* 2 + 1)。如果它比两个子节点的F值都低，就保持原位。反之，就把它和较低的子节点交换。那么，在这里，该元素的两个子节点的位置在 1 * 2 = 2和 1*2 + 1 = 3。显然，34不比任何一个子节点低，所以我们把它和较低的子节点，也就是17，交换。结果看起来是这样：

17 34 20 30 38 30 24

接着我们把它和新的子节点比较，它们在 2*2 = 4，和2*2 + 1 = 5的位置上。它不比任何一个子节点低，所以我们把它和较低的一个子节点交换（位置4上的30）。现在是这样：