对于二叉堆我们通常有三种操作：添加、删除和修改元素：
* 添加元素
首先把要添加的元素加到数组的末尾，然后和它的父节点（位置为当前位置除以2取整，比如第4个元素的父节点位置是2，第7个元素的父节点位置是3）比较，如果新元素比父节点元素小则交换这两个元素，然后再和新位置的父节点比较，直到它的父节点不再比它大，或者已经到达顶端，及第1的位置。
* 删除元素
删除元素的过程类似，只不过添加元素是“向上冒”，而删除元素是“向下沉”：删除位置1的元素，把最后一个元素移到最前面，然后和它的两个子节点比较，如果较小的子节点比它小就将它们交换，直到两个子节点都比它大。
* 修改元素
和添加元素完全一样的“向上冒”过程，只是要注意被修改的元素在二叉堆中的位置。
可以看出，使用二叉堆只需很少的几步就可以完成排序，很大程度上提高了寻路速度。
关于二叉堆先生需要了解的就是这么多了，下面来看看他怎么帮助元帅工作：
* 每次派出的“预备士兵”都会获得一个唯一的编号（ID），一直到寻路结束，它所有的数据包括位置、F值、G值、“父将”编号都将按这个ID存储。
* 每次有新的“开启士兵”加入，二叉堆先生将它的编号加入“开启士兵名录”并重新排序，使F值最低的ID始终排在最前面
* 当有“开启士兵”晋为“关闭将军”，删除“开启士兵名录”的第一个元素并重新排序
* 当某个“开启士兵”的F值被修改，更新其数据并重新排序
注意，“开启士兵名录”里存的只是人员的编号，数据全都另外存储。不太明白？没关系，元帅将在 第三部分 来次真刀实枪的大演兵。
经典论坛讨论:
http://bbs.blueidea.com/thread-2738527-1-1.html
地形数据不属于A*寻路的范围，这里定义一个 IMapTileModel 接口，由其它（模型）类来实现地图通路的判断。其它比如寻路超时的判断这里也不介绍，具体参考 AStar类及其测试代码。这里只介绍三部分主要内容：
* 数据存储
* 寻路过程
* 列表排序
数据存储
首先看看三个关键变量：
private var m_openList : Array; //开放列表，存放节点ID
private var m_openCount : int; //当前开放列表中节点数量
private var m_openId : int; //节点加入开放列表时分配的唯一ID(从0开始)
开放列表 m_openList 是个二叉堆（一维数组），F值最小的节点始终排在最前。为加快排序，开放列表中只存放节点ID ，其它数据放在各自的一维数组中：
private var m_xList : Array; //节点x坐标
private var m_yList : Array; //节点y坐标
private var m_pathScoreList : Array; //节点路径评分F值
private var m_movementCostList : Array; //(从起点移动到)节点的移动耗费G值
private var m_fatherList : Array; //节点的父节点(ID)
这些数据列表都以节点ID为索引顺序存储。看看代码如何工作：
//每次取出开放列表最前面的ID
currId = this.m_openList[0];
//读取当前节点坐标
currNoteX = this.m_xList[currId];
currNoteY = this.m_yList[currId];
还有一个很关键的变量：private var m_noteMap : Array;
//节点(数组)地图,根据节点坐标记录节点开启关闭状态和ID
使用 m_noteMap 可以方便的存取任何位置节点的开启关闭状态，并可取其ID进而存取其它数据。m_noteMap 是个三维数组，第一维y坐标（第几行），第二维x坐标（第几列），第三维节点状态和ID。判断点(p_x, p_y)是否在开启列表中：
return this.m_noteMap[p_y][p_x][NOTE_OPEN];
寻路过程
AStar类 寻路的方法是 find() :
/**
* 开始寻路
* @param p_startX 起点X坐标
* @param p_startY 起点Y坐标
* @param p_endX 终点X坐标
* @param p_endY 终点Y坐标
* @return 找到的路径(二维数组 : [p_startX, p_startY], ... , [p_endX, p_endY])
*/
public function find(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : Array{/* 寻路 */}
注意这里返回数据的形式：从起点到终点的节点数组，其中每个节点为一维数组[x, y]的形式。为了加快速度，类里没有使用Object或是Point，节点坐标全部以数组形式存储。如节点note的x坐标为note[0],y坐标为note[1]。
下面开始寻路，第一步将起点添加到开启列表：
this.openNote(p_startX, p_startY, 0, 0, 0);
openNote() 方法将节点加入开放列表的同时分配一个唯一的ID、按此ID存储数据、对开启列表排序。接下来是寻路过程：
while (this.m_openCount > 0)
{
//每次取出开放列表最前面的ID
currId = this.m_openList[0];
//将编码为此ID的元素列入关闭列表
this.closeNote(currId);
//如果终点被放入关闭列表寻路结束，返回路径
if (currNoteX == p_endX && currNoteY == p_endY)
return this.getPath(p_startX, p_startY, currId);
//...每轮寻路过程
}
//开放列表已空，找不到路径
return null;
每轮的寻路：
//获取周围节点，排除不可通过和已在关闭列表中的
aroundNotes = this.getArounds(currNoteX, currNoteY);
//对于周围每个节点
for each (var note : Array in aroundNotes)
{
//计算F和G值
cost = this.m_movementCostList[currId] + (note[0] == currNoteX || note[1] == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL;
score = cost + (Math.abs(p_endX - note[0]) + Math.abs(p_endY - note[1])) * COST_STRAIGHT;
if (this.isOpen(note[0], note[1])) //如果节点已在开启列表中
{
//测试节点的ID
checkingId = this.m_noteMap[note[1]][note[0]][NOTE_ID];
//如果新的G值比节点原来的G值小,修改F,G值，换父节点
if(cost < this.m_movementCostList[checkingId])
{
this.m_movementCostList[checkingId] = cost;
this.m_pathScoreList[checkingId] = score;
this.m_fatherList[checkingId] = currId;
//对开启列表重新排序
this.aheadNote(this.getIndex(checkingId));
}
} else //如果节点不在开放列表中
{
//将节点放入开放列表
this.openNote(note[0], note[1], score, cost, currId);
}
}
从终点开始依次沿父节点回到到起点，返回找到的路径：
/**
* 获取路径
* @param p_startX 起始点X坐标
* @param p_startY 起始点Y坐标
* @param p_id 终点的ID
* @return 路径坐标数组
*/
private function getPath(p_startX : int, p_startY : int, p_id: int) : Array
{
var arr : Array = [];
var noteX : int = this.m_xList[p_id];
var noteY : int = this.m_yList[p_id];
while (noteX != p_startX || noteY != p_startY)
{
arr.unshift([noteX, noteY]);
p_id = this.m_fatherList[p_id];
noteX = this.m_xList[p_id];
noteY = this.m_yList[p_id];
}
arr.unshift([p_startX, p_startY]);
this.destroyLists();
return arr;
}
列表排序
这
