A*寻路算法中的优化，取最小F值的时候特别时候使用最小堆
二叉树特点：是一颗完全二叉树；父节点要小于等于或者大于等于子节点。
其结构非常适合用数组描述。假设头结点为array[1]的二叉堆,则索引为i的节点，其父节点索引为i/2,其左子树索引12,右子树为i2+1。
移除堆顶的时候，将堆顶替换为末尾数据，size--,然后向下调整，若比子节点的大则互换，一直到没有互换或者成为叶子节点为止。
添加元素，在数组末尾加元素，向上调整，若比父节点小则互换，直到没有互换或者成功根节点为止。
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;//数组第一个元素，即index == 0 的位置上没有元素,从index==1的位置开始放置元素，这样方便对数组下标和元素位置进行统一操作
int m_size;//实际大小
private:
inline void SwapValue(int i,int j)
{
T temp=m_array[i];
m_array[i]=m_array[j];
m_array[j]=temp;
}
//获取父节点
inline int GetParentIndex(int index)
{
return (index-1)/2;
}
void AdjustUp(int start)
{
if(start==0)
return;
int currentIndex=start;//当前节点
int parentIndex=GetParentIndex(currentIndex);// 父节点
T currentValue=m_array[currentIndex];//当前节点的值
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;
}
