在A*寻路中使用二叉堆

很好，你可能会想，这的确有趣，但是如何把它付诸实施呢？嗯，关于二叉堆的一个有趣的事实是，你可以简单的把它存储在一个一维数组中。

在这个数组中，堆顶端的元素应该是数组的第一个元素(是下标1而不是0)。两个子节点会在2和3的位置。这两个节点的4个子节点应该在4－7的位置。

总的来说，任何元素的两个子节点可以通过把当前元素的位置乘以2（得到第一个子节点）和乘2加1（得到第二个子节点）来得到。就这样，例如堆中第三个元素（数值是20）的两个子节点，可以在位置2*3 = 6和2*3 +1 = 7这两个位置找到。那两个位置上的数字非别是30和24，当你查看堆的时候就能理解。

你其实不必要知道这些，除了表明堆中没有断层之外知道这些没有任何价值。7个元素，就完整的填满了一个三层堆的每一层。然而这并不是必要的。为了让我们的堆有效，我们只需要填充最底层之上的每一行。最底层自身可以是任意数值的元素，同时，新的元素按照从左到右的顺序添加。这篇文章描述的方法就是这样做的，所以你不必多虑。

往堆中添加新元素

当我们实际在寻路算法中使用二叉堆的时候，还需要考虑更多，但是现在我们只是学习一下如何使用二叉堆。我跳过这部分以便更容易理解基本的东西。我会在文章后面的部分给出处理这一切的完整公式，但了解这些细节仍然十分重要。

大致的，为了往堆里添加元素，我们把它放在数组的末尾。然后和它在 当前位置/2 处的父节点比较，分数部分被圆整。如果新元素的F值更低，我们就交换这两个元素。然后我们比较这个元素和它的新父节点，在 （当前位置）/2 ，小数部分圆整，的地方。如果它的F值更低，我们再次交换。我们重复这个过程直到这个元素不再比它的父节点低，或者这个元素已经到达顶端，处于数组的位置1。