在A*寻路中使用二叉堆

　2006-07-23 11:33:11　来源：WEB开发网　　　

核心提示： 无疑，我们不能只建立堆，在A*寻路中使用二叉堆(8)，当不需要的时候，我们也要从堆中删除元素，这确保了你把它和较低的子节点交换，如果做错会造成不完整的堆，特别的，在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