A*尋路算法中的優(yōu)化，取最小F值的時(shí)候特別時(shí)候使用最小堆

二叉樹特點(diǎn)：是一顆完全二叉樹；父節(jié)點(diǎn)要小于等于或者大于等于子節(jié)點(diǎn)。

其結(jié)構(gòu)非常適合用數(shù)組描述。假設(shè)頭結(jié)點(diǎn)為array[1]的二叉堆,則索引為i的節(jié)點(diǎn)，其父節(jié)點(diǎn)索引為i/2,其左子樹索引12,右子樹為i2+1。

移除堆頂?shù)臅r(shí)候，將堆頂替換為末尾數(shù)據(jù)，size--,然后向下調(diào)整，若比子節(jié)點(diǎn)的大則互換，一直到?jīng)]有互換或者成為葉子節(jié)點(diǎn)為止。

添加元素，在數(shù)組末尾加元素，向上調(diào)整，若比父節(jié)點(diǎn)小則互換，直到?jīng)]有互換或者成功根節(jié)點(diǎn)為止。

include <iostream>

include <vector>

using namespace std;

struct Point
{
int F;
int G;
int H;

Point(int g,int h):G(g),H(h){F=G+H;}

inline bool operator<(const Point &point)
{
    return F<point.F;
}

inline bool operator>(const Point& point)
{
    return F>point.F;
}

void operator=(const Point& point)
{
     F=point.F;
     G=point.G;
     H=point.H;
}

friend ostream& operator<<(ostream& out,Point& point)
{
    out<<"F:"<<point.F<<"    G:"<<point.G<<"    H:"<<point.H<<endl;
    return out;
}

};

//二叉堆算法,最小堆
template<class T>
class BinaryHeap
{
public:
BinaryHeap():m_size(0){}
BinaryHeap(int capacity)
{
m_size=0;
m_array.reserve(capacity);
}

void Clear()
{
    m_size=0;
    m_array.clear();
}

T Front()
{
    if(!m_array.empty())
    {
        return m_array[0];
    }
    else
    {
        return 0;
    }
}

//彈出頂元素
T Pop()
{
    T temp = m_array[0];
    m_array[0]=m_array[--m_size];
    m_array.pop_back();
    AdjustDown();
    return temp;
}

T Push(T elem)
{
    m_array.push_back(elem);
    ++m_size;
    AdjustUp(m_size-1);
    return elem;
}

private:
vector<T> m_array;//數(shù)組第一個(gè)元素，即index == 0 的位置上沒有元素,從index==1的位置開始放置元素，這樣方便對數(shù)組下標(biāo)和元素位置進(jìn)行統(tǒng)一操作
int m_size;//實(shí)際大小

private:
inline void SwapValue(int i,int j)
{
T temp=m_array[i];
m_array[i]=m_array[j];
m_array[j]=temp;
}

//獲取父節(jié)點(diǎn)
inline int GetParentIndex(int index)
{
    return (index-1)/2;
}

void AdjustUp(int start)
{
    if(start==0)
        return;

    int currentIndex=start;//當(dāng)前節(jié)點(diǎn)
    int parentIndex=GetParentIndex(currentIndex);// 父節(jié)點(diǎn)
    T currentValue=m_array[currentIndex];//當(dāng)前節(jié)點(diǎn)的值

    while (parentIndex>=0)
    {
        if(m_array[parentIndex] < currentValue || currentIndex==parentIndex)
            break;
        else
        {
            SwapValue(parentIndex,currentIndex);
            currentIndex=parentIndex;
            parentIndex=GetParentIndex(currentIndex);
        }
    }
}

void AdjustDown()
{
    int currentIndex=0;
    while (currentIndex<m_size)
    {
        int leftIndex=2*currentIndex+1;
        int rightIndex=leftIndex+1;

        if(leftIndex<m_size&&m_array[leftIndex]<m_array[currentIndex])
        {
            if(rightIndex<m_size&&m_array[rightIndex]<m_array[currentIndex]&&m_array[rightIndex]<m_array[leftIndex])
            {
                leftIndex=rightIndex;
            }

            SwapValue(leftIndex,currentIndex);
            currentIndex=leftIndex;
        }
        else
        {
            break;
        }
    }
}

};

int main(){
//priority_queue<int> q;
// priority_queue<int, vector<int>, greater<int> > q;
// for( int i= 0; i< 10; ++i )
// q.push( rand() );
//
// while( !q.empty() )
// {
// cout << q.top() << endl;
// q.pop();
// }
// getchar();

cout<<"--------------依次壓入----------------"<<endl;
BinaryHeap<Point> heap;
for (int i=0;i<20;i++)
{
    Point p(rand(),rand());
    heap.Push(p);
    cout<<p<<endl;
}

cout<<"---------------依次彈出----------------"<<endl;
for (int i=0;i<20;i++)
{
    cout<<heap.Pop()<<endl;
}

getchar();

return 0;  

}