在A*寻路中使用二叉堆

核心提示： 17 30 20 34 38 30 24最后一次，我们比较它和新的子节点，在A*寻路中使用二叉堆(5)，照例，子节点在位置 4*2 = 8和4*2+1 = 9的位置上，堆最顶端的元素被存储在openList(1)，第二个元素在openList(2)，但是那些位置上并没有元素，因为列表没那么

17 30 20 34 38 30 24

最后一次，我们比较它和新的子节点。照例，子节点在位置 4*2 = 8和4*2+1 = 9的位置上。但是那些位置上并没有元素，因为列表没那么长。我们已经到达了堆的底端，所以我们停下来。

二叉堆为什么这么快？

现在你知道了堆基本的插入和删除方法，你应该明白为什么它比其他方法，比如说插入排序更快。假设你有个有1000个节点的开启列表，在一格有很多节点的相当大的地图上，这不是不可能（记住，即使是100×100的地图，上面也有10,000个节点）。如果你使用插入排序，从起点开始，到找到新元素恰当的位置，在把新元素插入之前，平均需要做500次比较。

使用二叉堆，你从底端开始，可能只要1－3次比较就能把新元素插入到正确的位置。你还需要9次比较用来从开启列表中移除一个元素，同时保持堆仍然有序。在A*中，你通常每次只需要移除一个元素(F值最低的元素)，在任意位置添加0到5个新节点(就像主文章里描述的2D寻路)。这总共花费的时间大约是同样数量节点进行插入排序的1%。差别随你地图的增大(也就是节点更多)呈几何增长。地图越小，就越没优势，这也是为什么你的地图和节点越少，二叉堆的价值就越低的原因。

顺便，使用二叉堆并不意味着你的寻路算法会快100倍。在下面还讲了一些棘手的问题。额外的，A*不仅仅是为开启列表排序。然而，根据我的经验，用二叉堆在大部分场合可以提高2－3倍的速度，更长的路径，速度提高的更多。

创建开启列表数组

现在我们了解了二叉堆，那么如何使用它呢？首先要做的是构造我们的一维数组。为此，我们先要确定它的大小。一般来说，列表大小不会超过地图上的节点总数（在最坏的情况下，我们搜索整个地图寻找路径）。在一个方形二维地图中，就如我的主文章中描述的，我们的节点不超过 地图宽 × 地图高。那么我们的一维数组就是那个大小。在这个例子里，我们叫这个数组 openList()。堆最顶端的元素被存储在openList(1)，第二个元素在openList(2)，依此类推。