二叉堆是一种特殊的堆，二叉堆是完全二元树或者是近似完全二元树。二叉堆满足堆特性：父结点的键值总是大於或等于任何一个子节点的键值。
存储
二叉堆一般用数组来表示。例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2。因此，第0个位置的子节点在2和3，1的子节点在4和5。以此类推。这种存储方式便於寻找父节点和子节点。
如下图的两个堆：
1 11
/ /
2 3 9 10
/ / / /
4 567 5 67 8
/ / / /
89 10 11 12 34
将这两个堆保存在以1开始的数组中：
位置:123456789 10 11
左图:123456789 10 11
右图: 119 1056781234
基本操作
在二叉堆上可以进行插入节点、删除节点、取出值最小的节点、减小节点的值等基本操作。
如何让a*寻路更快？元帅三顾茅庐，请来南阳二叉堆先生帮忙优化寻找“开启士兵名录”中最低f值的过程，将寻路速度提高了2到3倍，而且越大的地图效果越明显。下面隆重介绍二叉堆先生：
下图是一个二叉堆的例子，形式上看，它从顶点开始，每个节点有两个子节点，每个子节点又各自有自己的两个子节点；数值上看，每个节点的两个子节点都比它大或和它相等。
在二叉堆里我们要求：
* 最小的元素在顶端
* 每个元素都比它的父节点大，或者和父节点相等。
只要满足这两个条件，其他的元素怎么排都行。如上面的例子，最小的元素10在最顶端，第二小的元素20在10的下面，但是第三小的元素24在20的下面，也就是第三层，更大的30反而在第二层。
这样一“堆”东西我们在程序中怎么用呢？幸运的是，二叉堆可以用一个简单的一维数组来存储，如下图所示。
假设一个元素的位置是n（第一个元素的位置为1，而不是通常数组的第一个索引0），那么它两个子节点分别是 n × 2 和 n × 2 + 1 ，父节点是n除以2取整。比如第3个元素（例中是20）的两个子节点位置是6和11，父节点位置是1。
对于二叉堆我们通常有三种操作：添加、删除和修改元素：
* 添加元素
首先把要添加的元素加到数组的末尾，然后和它的父节点（位置为当前位置除以2取整，比如第4个元素的父节点位置是2，第7个元素的父节点位置是3）比较，如果新元素比父节点元素小则交换这两个元素，然后再和新位置的父节点比较，直到它的父节点不再比它大，或者已经到达顶端，及第1的位置。
* 删除元素
删除元素的过程类似，只不过添加元素是“向上冒”，而删除元素是“向下沉”：删除位置1的元素，把最后一个元素移到最前面，然后和它的两个子节点比较，如果较小的子节点比它小就将它们交换，直到两个子节点都比它大。
* 修改元素
和添加元素完全一样的“向上冒”过程，只是要注意被修改的元素在二叉堆中的位置。
可以看出，使用二叉堆只需很少的几步就可以完成排序，很大程度上提高了寻路速度。
关于二叉堆先生需要了解的就是这么多了，下面来看看他怎么帮助元帅工作：
* 每次派出的“预备士兵”都会获得一个唯一的编号（id），一直到寻路结束，它所有的数据包括位置、f值、g值、“父将”编号都将按这个id存储。
* 每次有新的“开启士兵”加入，二叉堆先生将它的编号加入“开启士兵名录”并重新排序，使f值最低的id始终排在最前面
* 当有“开启士兵”晋为“关闭将军”，删除“开启士兵名录”的第一个元素并重新排序
* 当某个“开启士兵”的f值被修改，更新其数据并重新排序
注意，“开启士兵名录”里存的只是人员的编号，数据全都另外存储。不太明白？没关系，元帅将在 第三部分 来次真刀实枪的大演兵。 |