AStar 在每次主循環(huán)中都要在 openList 中找到一個(gè) F 值最小的節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)稠炬。之前的 openList 使用簡(jiǎn)單的數(shù)組來(lái)實(shí)現(xiàn)，當(dāng)在其中搜尋最小節(jié)點(diǎn)時(shí)把整個(gè) openList 遍歷一遍找到最小的節(jié)點(diǎn)钾挟。這是一個(gè)可以優(yōu)化的點(diǎn)。
為 openList 維護(hù)一個(gè)有序表
因?yàn)橐?openList 中找到最小節(jié)點(diǎn)饱岸，一個(gè)比較容易想到的辦法是把 openList 排序掺出，然后每次都取這個(gè)表的第一個(gè)（升序）或者最后一個(gè)（降序）節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)。
但是苫费，如果采用快速排序?qū)?openList 排序的話汤锨，每次主循環(huán)內(nèi)都要付出平均 O(n*log(n)) 的代價(jià)，而遍歷搜索的平均代價(jià)為 O(n) 百框∧喑基于這個(gè)粗略的估計(jì)，維護(hù)一個(gè)有序表似乎對(duì)提高算法速度并沒(méi)有什么幫助琅翻。
使用二叉堆
二叉堆是一棵完全二叉樹位仁，它的每一個(gè)節(jié)點(diǎn)都小于（小頂堆）或者大于（大頂堆）它的左右兒子。
因?yàn)槎娑训男再|(zhì)方椎，找到它最小或者最大的節(jié)點(diǎn)花費(fèi)的時(shí)間是常量的聂抢，即 O(1)。
AStar 算法在找到當(dāng)前節(jié)點(diǎn)后還要在 openList 中移除這個(gè)節(jié)點(diǎn)棠众，移除這個(gè)節(jié)點(diǎn)后就需要重新調(diào)整二叉堆的結(jié)構(gòu)一滿足它最小節(jié)點(diǎn)在樹根的性質(zhì)琳疏。這里采用的方法是將樹的最后一個(gè)節(jié)點(diǎn)移動(dòng)到樹根有决，然后不斷向分支尋找這個(gè)節(jié)點(diǎn)的位置，直到找到它的合適位置空盼，這個(gè)過(guò)程的平均時(shí)間復(fù)雜度是 O(log(n))书幕。這個(gè)過(guò)程稱為“下濾”。
二叉堆在插入新的節(jié)點(diǎn)之后也要調(diào)整結(jié)構(gòu)以滿足性質(zhì)揽趾。這里采用的方法是在完全二叉樹的最后一個(gè)節(jié)點(diǎn)之后插入一個(gè)新的節(jié)點(diǎn)台汇，然后不斷向上調(diào)整這個(gè)節(jié)點(diǎn)，直到找到它的合適位置篱瞎，這個(gè)過(guò)程的平均時(shí)間復(fù)雜度是 O(log(n))苟呐。這個(gè)過(guò)程稱為“上濾”。
綜上俐筋，在以正方形為基本節(jié)點(diǎn)的地圖中的 AStar 算法中使用二叉堆來(lái)實(shí)現(xiàn) openList 的總的時(shí)間復(fù)雜度是：
O(1) + O(log(n)) + m * O(log(n))
其中 m 是每次檢測(cè)加入的新節(jié)點(diǎn)的個(gè)數(shù)牵素。
下面是代碼:
接口：
template <typename BinaryHeapNode>
class BinaryHeap {
public:
BinaryHeap(); //構(gòu)造函數(shù)
bool empty(); //二叉堆是為空
BinaryHeapNode getMin(); //得到最小節(jié)點(diǎn)
BinaryHeapNode isIn(const BinaryHeapNode &node); //判斷一個(gè)節(jié)點(diǎn)是否在二叉堆中
void insert(const BinaryHeapNode &node); //插入一個(gè)節(jié)點(diǎn)
void deleteMin(); //刪除最小節(jié)點(diǎn)
private:
int _currentSize; //二叉堆的 size
std::vector<BinaryHeapNode> _array; //節(jié)點(diǎn)采用 vector 儲(chǔ)存
void _percolateUp(int hole); //上濾
void _percolateDown(int hole); //下濾
};
實(shí)現(xiàn)：
template <typename BinaryHeapNode>
BinaryHeap<BinaryHeapNode>::BinaryHeap(){
//構(gòu)造函數(shù)，初始化二叉堆的大小為 0澄者，并為節(jié)點(diǎn)的儲(chǔ)存 vector 分配一個(gè)初始尺寸
_currentSize = 0;
_array.resize(100);
}
template <typename BinaryHeapNode>
bool BinaryHeap<BinaryHeapNode>::empty(){
//判空方法
if (_currentSize == 0){
return true;
}
return false;
}
template <typename BinaryHeapNode>
BinaryHeapNode BinaryHeap<BinaryHeapNode>::isIn(const BinaryHeapNode &node){
//判斷一個(gè)節(jié)點(diǎn)是否在這個(gè)二叉堆中笆呆，簡(jiǎn)單的遍歷儲(chǔ)存節(jié)點(diǎn)的 vector 來(lái)判斷是否存在這個(gè)節(jié)點(diǎn)
//因?yàn)?vector 中儲(chǔ)存的是 AStarNode 的指針，如果想要調(diào)用重載的 == 運(yùn)算符需要對(duì)這個(gè)節(jié)點(diǎn)解一次引用粱挡，下同
for (int index = 1; index <= _currentSize; ++index){
if ((*node) == _array[index]){
return _array[index];
}
}
return nullptr;
}
template <typename BinaryHeapNode>
BinaryHeapNode BinaryHeap<BinaryHeapNode>::getMin(){
//返回二叉堆的第一個(gè)節(jié)點(diǎn)腰奋，然后從二叉堆中刪除它
BinaryHeapNode min = _array[1];
deleteMin();
return min;
}
template <typename BinaryHeapNode>
void BinaryHeap<BinaryHeapNode>::insert(const BinaryHeapNode &node){
//向二叉堆中插入一個(gè)節(jié)點(diǎn)
//首先判斷 vector 的空間是否已經(jīng)用完，如果已經(jīng)用完重新分配當(dāng)前需要空間二倍的空間抱怔，避免頻繁的調(diào)用 resize
//然后將新元素插入二叉堆的最后一個(gè)元素的后面劣坊，接著執(zhí)行“上濾”操作
int hole = ++_currentSize;
if (_array.size() - 1 <= _currentSize){
_array.resize(_currentSize * 2);
}
_array[_currentSize] = node;
_percolateUp(hole);
}
template <typename BinaryHeapNode>
void BinaryHeap<BinaryHeapNode>::deleteMin(){
//刪除二叉堆中最小的元素
//使用最后一個(gè)元素覆蓋第一個(gè)元素，然后對(duì)第一個(gè)元素執(zhí)行“下濾”操作
_array[1] = _array[_currentSize--];
_percolateDown(1);
}
template <typename BinaryHeapNode>
void BinaryHeap<BinaryHeapNode>::_percolateDown(int hole){
//下濾
int child;
BinaryHeapNode temp = _array[hole]; //先找到將要下濾的元素備用
for (; hole * 2 <= _currentSize; hole = child){ //如果這個(gè)元素不是葉節(jié)點(diǎn)進(jìn)入循環(huán)
child = hole * 2; //獲得這個(gè)元素的左兒子指針
if (child != _currentSize && (*_array[child + 1]) < _array[child]){
//如果這個(gè)元素的左兒子不是最后一個(gè)元素并且右兒子比左兒子還小屈留，意味著如果這個(gè)元素要向下交換的話也要和右兒子交換局冰，所以把指針移向右兒子
++child;
}
//交換操作
if ((*_array[child]) < temp){
_array[hole] = _array[child];
}else {
break;
}
}
_array[hole] = temp;
}
template <typename BinaryHeapNode>
void BinaryHeap<BinaryHeapNode>::_percolateUp(int hole){
//上濾
//不斷的和當(dāng)前位置的父節(jié)點(diǎn)做比較判斷是否需要交換
for (; hole > 1 && (*_array[hole]) < _array[hole / 2]; hole /= 2){
BinaryHeapNode tempNode = _array[hole];
_array[hole] = _array[hole / 2];
_array[hole / 2] = tempNode;
}
}