在A*寻路中使用二叉堆

核心提示： 二叉堆二叉堆和刚才说的快速排序很像，经常被那些苛求A*速度的人使用，在A*寻路中使用二叉堆(2)，根据我的经验，二叉堆平均提高寻路速度2-3倍，这就可以了，这些条件在这里都完全符合，对于包含大量节点的地图(也就是说100×100节点或者更多）效果更明显，友情提醒

二叉堆

二叉堆和刚才说的快速排序很像，经常被那些苛求A*速度的人使用。根据我的经验，二叉堆平均提高寻路速度2-3倍，对于包含大量节点的地图(也就是说100×100节点或者更多）效果更明显。友情提醒，然而二叉堆很难处理，除非你使用含有大量节点的地图，速度至关重要，否则不值得为它头痛。

文章其他的部分深入说明了二叉堆和它在A*算法中的用途。如果你对我的文章存有疑惑，在文章末尾进一步阅读的小节中提供了更多的观点。

仍然有兴趣？好，我们继续。。。

在有序列表中，每个元素都按照由低到高或由高到低的顺序保存在恰当的位置。这很有用，但是还不够。事实上，我们并不关心数字127是否比128在更低的位置上。我们只是想让F值最低的元素能放在列表顶端以便容易访问。列表的其他部分即使是混乱的也不必在意。列表的其他部分只有在我们需要另一个F值最低的元素的时候，才有必要保持有序。

基本上，我们真正需要的是一个“堆”，确切的说，是个二叉堆。二叉堆是一组元素，其中最大或者最小（取决于需要）的元素在堆顶端。既然我们要寻找F值最小的元素，我们就把它放在堆顶端。这个元素有两个子节点，每个的F值等于，或者略高于这个元素。每个子节点又有两个子节点，他们又有和他们相等或略高的子节点。。。依次类推。这里是一个堆可能的样子：

注意，F值最低的元素(10)在最顶端，第二低的元素(20)是它的一个子节点。可是，其后就没有任何疑问了。在这个特定的二叉堆里，第三低的元素是24，它离堆顶有两步的距离，它比30小，但是30却在左侧离堆顶一步之遥的地方。简单的堆放，其他的元素在堆的哪个位置并不重要，每个单独的元素只需要和它的父节点相等或者更高，而和它的两个子节点相比，更低或者相等，这就可以了。这些条件在这里都完全符合，所以这是个有效的二叉堆。