前言(萌新感想)：
以前用STL的queue啊stack啊priority_queue啊，一直很想懂原理，现在终于课上到了priority_queue，还有就是下周期中考，哈哈，所以写几篇blog总结一下。
这里萌新讲下堆这个好东西；
堆的定义：
如果搞过ACM的童鞋应该会使用STL的priority_queue，堆就是STL的priority_queue。
堆是一种特殊的队列，从堆中取元素的依据是元素优先权大小，而不是元素进入队的先后顺序；
直接切入主题吧；
堆最常用的结构是二叉树，一棵完全二叉树，而完全二叉树由于其结点特别规律，所以可以用数组直接模拟。
下面介绍几个堆(以完全二叉树的形式)：
最大堆：每个结点上的元素不小于其子节点元素的值；
最小堆：每个结点上的元素不大于其子节点元素的值；
拿最大堆来讲几个操作：
创建，插入，删除，建立最大元素；
下面参考自陈越姥姥版数据结构
用C语言(窝觉得好**)描述最大堆结构；
先定义：
typedef struct HeapStruct* MaxHeap;
struct HeapStruct
{
int *Elements; //存储元素的数组；
int Size; //堆的当前元素；
int Capacity; //堆的最大容量；
};
有人会说，卧槽为什么要结构体啊，明明说好的数组可以直接处理，为毛不用数组啊，而且结构体里面还有指针，好烦(繁)啊！
萌新想说，这样严谨吧，其实差不多啊，无非是换种方式而已；PS：ACM中不是很常用指针吧，说错，不是不常用指针，而是不常用动态开辟内存，时间很慢。
而且指针如果用的灵活，那是很超神的能力啊！
创建最大堆：
其实。。。他就是动态开辟了一个内存，然后存了一个东西。初学者不用太深究(搞不懂就先放放，先吃西瓜，再捡芝麻)。
MaxHeap Creat(int MaxSize) //创建容量为MaxSize 空的最大堆
{
MaxHeap H;
int INF=0x3f3f3f3f;
H=(MaxHeap)malloc(sizeof(struct HeapStruct)); //都是动态开辟内存，不用深究
H->Elements=(int *)malloc((MaxSize+1)*sizeof(int));
H->Size=0; //初始化为0；
H->Elements[0]=INF; //作为一个”哨兵“为大于堆中所有可能元素的值；
return H;
}
最大堆的插入：
首先判断堆 是不是已经满了；
我们先假设这个元素插在了Size+1这个结点上，
①：他比他的父节点的值小，OK，那就躺着吧，插入完成；
②：可惜他比他的父节点大啊，那么。。。交换就好了嘛，交换以后一定是合法的啊。
这里有一种写法很牛逼啊，比普通交换好很多；
我们先假设这个元素插在了Size+1这个结点上，
①：他比他的父节点的值小，OK，那就躺着吧，插入完成；
②：可惜他比他的父节点大啊，那么。。。交换就好了嘛，交换以后一定是合法的啊。
这里有一种写法很牛逼啊，比普通交换好很多；
void Insert(MaxHeap H,int item) //item 是要插入的元素，这里称目标；
{
int i;
if(isFull(H)) //先判断一下是不是已经满了
{
printf("最大堆已满\n");
return;
}
i=++H->Size; //先默认目标被插在了新开的结点
//对下面的循环细说一下，如果目标比他的父节点大的话，那么交换，可以看到目标并没有存到父节点上，然后i/=2使得往上继续判断，如果>目标就会弹出循环；
//最后很有可能他成了整个完全二叉树的根，这里目标的编号是1，所以这个编号0就发挥作用了，一定比他大啊；
for( ; H->Elements[i/2] < item; i/=2)
H->Elements[i]=H->Elements[i/2];
H->Elements[i]=item;
}
最大堆的删除：
萌新把 根 称做爷爷吧。
一开始爷爷做主。
我们浅显地可以看到拿走了最大的元素(即爷爷被带走了)，那么肯定就是要个大的子结点(最大的爸爸)来顶替他的位置。
然后处理大的那个子节点被顶替上去了，所以又要安排一个最大的孙子顶替。
所以一直一直要处理好，但是你这样一直一直顶替会有个问题，可能会构造不成一棵完全二叉树。
一开始爷爷做主。
我们浅显地可以看到拿走了最大的元素(即爷爷被带走了)，那么肯定就是要个大的子结点(最大的爸爸)来顶替他的位置。
然后处理大的那个子节点被顶替上去了，所以又要安排一个最大的孙子顶替。
所以一直一直要处理好，但是你这样一直一直顶替会有个问题，可能会构造不成一棵完全二叉树。
处理方法是把最后一个元素拿出来，以这个元素作为替补，因为根已经被删除了，然后就从根往下遍历，如果一旦存在这个元素可以填的位置，就填上去，一定能够保证是一个完全二叉树了；
bool isFull(MaxHeap H)
{ }
void DeleteMax(MaxHeap H)
{
int Parent,Child;
int temp;
if(IsEmpty(H))
{
printf("堆为空\n");
return;
}
temp=H->Elements[H->Size--]; //取末尾元素
//从根开始填
for(Parent=1; Parent*2<=H->Size; Parent = Child)
{
Child=Parent*2;
if(Child!=H->Size&&(H->Elements[Child+1]>H->Elements[Child])) //如果没有右儿子就是左儿子，如果有在左右儿子节点找一个大的，
Child++;
if(temp>=H->Elements[Child]) //如果比末尾元素比两个儿子都大，直接填他就行了
break;
else
H->Elements[Parent]=H->Elements[Child]; //不是的话就替换，然后往下继续判断；
}
H->Elements[Parent]=temp;
}
最大堆的建立：
大致思路就是从底层开始判断，因为完全二叉树的编号很规律，从size/2也就是最后一个结点的父节点开始判断，每次往下看看这个结点能放到哪个位置，
然后依次减减减，也就是判断每一层的结点啊；
然后依次减减减，也就是判断每一层的结点啊；
void BuildMaxHeap(MaxHeap H)
{
int i,Parent,Child;
int temp;
for(i=H->Size/2; i>0 ; --i)
{
temp=H->Elements[i];
for(Parent=i; Parent*2<=H->Size; Parent=Child)
{
Child=Parent*2;
if(Child!=H->Size&&(H->Elements[Child+1]>H->Elements[Child])) //如果没有右儿子就是左儿子，如果有在左右儿子节点找一个大的，
Child++;
if(temp>=H->Elements[Child]) //如果比末尾元素比两个儿子都大，直接填他就行了
break;
else
H->Elements[Parent]=H->Elements[Child]; //不是的话就替换，然后往下继续判断；
}
H->Elements[Parent]=temp;
}
}
OK,欢迎提出意见~~~~~