在A寻路中使用二叉堆

从堆中删除元素(第二部分)

无疑，我们不能只建立堆，当不需要的时候，我们也要从堆中删除元素。特别的，在A*寻路中，我们在检查和切换到关闭列表之后，从堆顶需要删除F值最低的元素。

如前所述，你从把末元素移动到堆顶开始，然后把堆中的元素总数减1。伪代码是这样：

openList(1) = openList(numberOfOpenListItems)
numberOfOpenListItems = numberOfOpenListItems - 1

接着我们需要依次比较它和两个子节点的数值。如果它的F值更高，我们就把它和更低F值的子节点交换。然后我们把它和新的子节点比较（看它是否更低）。如果它的F值比两个子节点更高，我们把它和较低的一个交换。我们重复这个过程直到找到它的正确位置，这可能会一直持续到堆底，但并不是完全必要。伪代码看起来是这样：

v = 1
;Repeat the following until the item sinks to its proper spot in the binary heap.
Repeat
　　u = v
　　If 2*u+1 <= numberOfOpenListItems ;if both children exist
　　　　;Select the lowest of the two children.
　　　　If Fcost(openList(u)) >= Fcost(openList(2*u))then v = 2*u ;SEE NOTE BELOW
　　　　If Fcost(openList(v)) >= Fcost(openList(2*u+1))then v = 2*u+1 ;SEE NOTE BELOW
　　Else If 2*u <= numberOfOpenListItems ;if only child #1 exists
　　　　;Check if the F cost is greater than the child
　　　　If Fcost(openList(u)) >= Fcost(openList(2*u))then v = 2*u
　　End If
　　If u <> v then ; If parent''s F > one or both of its children, swap them
　　　　temp = openList(u)
　　　　openList(u) = openList(v)
　　　　openList(v) = temp
　　Else
　　　　Exit ;if item <= both children, exit repeat/forever loop
　　End if
Forever ;Repeat forever

请注意两行代码中粗体(红色)的u和v的数值。在第二行，你应该使用 v而不是u，这不是很显而易见。这确保了你把它和较低的子节点交换。如果做错会造成不完整的堆，完全打乱你的寻路。

对开启列表的元素重排序

就如在主文章中描述的，有时候你会发现现有的开启列表中的元素会改变。这种情况发生的时候，我们不必要取出这个元素重新来过。只要从当前位置开始，用它新的（更低的）F值和它的父节点比较。如果它的F值低到足以替换它的父节点，你就把它替换掉（不然你就会得到一个错误的堆，一切都完了）。一般，你使用和“在堆中添加新元素”的小节中相同的代码，并做额外处理如下：

不幸的是，因为你的数据是在一个庞大，无序的堆里，你需要遍历整个堆查找先有开启列表中的元素。你主要要查找由openX(openList()) 和openY(openList())获取的确切坐标的格子，找到之后，你就可以从那一点开始，像往常那样做必要的比较和交换。

最后的注解

好了，我希望你仍然能读懂，没有被搞昏头。如果你不着急，并且希望在自己的寻路算法中使用二叉堆，那么这就是我的建议。

首先，把二叉堆放一放。把注意力放在你的A*寻路算法上，使用简单点的排序算法，保证算法正常工作没有bug。一开始你并不需要它很快速，你只需要它能工作。

其次，在你把二叉堆添加到代码中之前，试着把二叉堆写成独立的功能，用适当的方法添加和删除元素。确保你写的程序中，可以看到整个过程中每一步的操作，也许可以把结果打印在屏幕上，如果你愿意。你还得包含一些中途退出的代码，以便在必要的时候结束整个流程。如果二叉堆写的不对，你很容易就会陷入到无限循环中。

一旦你确信两个程序都运行无误，备份他们，然后开始把他们结合起来。除非你比我还聪明，否则一开始你难免遇到麻烦。输出都是些错误信息 并且/或者 看到寻路者因为bug走出各种怪异的方向。不过最终你会搞定一切。

进一步阅读

和以往一样，网上有很多其他的关于这个话题的好文章。这里有些入门的。第一篇用图示。第二篇说明了怎么用一个简单的数组（如果我的说明很麻烦的话）实现二叉堆。第三篇探讨了寻路算法中堆的一般用途。

http：//www.onthenet.com.au/~grahamis/int2008/week11/lect11.html；

http：//www.purists.org/pqueue/；

http：//theory.stanford.edu/~amitp/GameProgramming/ImplementationNotes.html#S5；

最后，你可能想看看我的寻路代码，这里可以找到。它和文中的伪代码相互照应，注释详尽，有C++和Blitz两个版本，Blitz是一个比其他大多数都容易理解的语言。不使用C++的程序员会很容易理解Basic版本的代码。