最小堆的大建立及其一些基本操作

最小堆，能够维护最的的元素的最上面。同样还有最大堆等

#include <stdio.h>

#include<stdlib.h>

typedef int ElementType;
ElementType MinDate = -10000 ;
struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int Maxelement);       //创建并初始化
void Destory(PriorityQueue H);                      //销毁最小堆
void MakeEmpty(PriorityQueue H);                //清空堆
void Insert(ElementType X,PriorityQueue H);    //插入X
ElementType DeleteMin(PriorityQueue H);        //删除堆中最小值
ElementType FindMin(PriorityQueue H);            //查找最小值，返回最小值
int IsEmpty(PriorityQueue H);                            //判空
int IsFull(PriorityQueue H);                                //判满


int main(void)        //主函数，最小堆，利用顺序储存结构
{
PriorityQueue H;
H = Initialize(40);

Insert(45,H);
Insert(11,H);
Insert(30,H);
Insert(88,H);


printf("%d\n",FindMin(H));

//   printf("Hello World!\n");
return 0;
}

struct HeapStruct
{
int Capacity;\
int Size;
ElementType *Elements;
};

PriorityQueue Initialize(int Maxelement)                    //创建并初始化一个最小堆
{
PriorityQueue H;

H = (PriorityQueue)malloc(sizeof(struct HeapStruct));   //为总的结构体发配空间
if( NULL == H)
{
printf("Out of Space\n");
}
//为结构体中数组发配空间，其中储存每个元素
H->Elements =  (ElementType*)malloc((Maxelement + 1) * sizeof(ElementType));
if(NULL == H->Elements )
{
printf("Out of Space\n");
}

H->Capacity = Maxelement;                       //储存数组最大值
H->Size = 0;                                    //初始化size
H->Elements[0] = MinDate;                       //初始化最小值

return H;
}

void Insert(ElementType X, PriorityQueue H)
{
int i;

if(IsFull(H))                                       //判满
{
printf("Priority Is Full\n");
}                                                   //每次插入一次，size++一次。建立一个空穴
for(i = ++H->Size; H->Elements[i / 2] > X;i /= 2)   //如果X小于父亲的值，空穴上移一层
{
H->Elements[i] = H->Elements[i/2];
}
H->Elements[i] = X;                                 //将X填入空穴

}



void Destory(PriorityQueue H)
{
free(H->Elements);
free(H);
}

void MakeEmpty(PriorityQueue H)
{
H->Size = 0;
}

/*
删除最小元比较容易，因为堆中第一个元素就是最小元。难的是删除最小元后，怎么维护这个最小堆。
一种思路是，将儿子节点中较小的那个提为父亲，一直这样下去，直到最后一层。也就是将空穴一直
沿着最小元传递下去
*/
ElementType DeleteMin(PriorityQueue H)          //删除堆中最小值
{
int i,Child;
ElementType MinElement,LastElement;
if(IsEmpty(H))
{
printf("Priority Is Empty\n");
return H->Elements[0];

}

MinElement = H->Elements[1];                //堆中最小的元素
LastElement = H->Elements[H->Size--];       //堆中最后一个元素，因为从数组从1开始，所以要size--
//并且size--，也标志着数组中元素减一
for(i = 1; i * 2 <= H->Size; i = Child )
{
Child = 2 * i;
if(Child != H->Size && H->Elements[Child + 1] < H->Elements[Child]) //找到左右孩子中较小的
Child++;

if(LastElement > H->Elements[Child])
H->Elements[i] = H->Elements[Child];
else
break;

}

H->Elements[i] = LastElement;

return MinElement;
}

ElementType FindMin(PriorityQueue H)                //堆中最小元为数组下标为1的元素
{
if(IsEmpty(H))
{
printf("Priority Is Empty\n");
return H->Elements[0];
}

return H->Elements[1];
}

int IsEmpty(PriorityQueue H)                    //如果数组大小为0的话，数组为空
{
return H->Size == 0;
}

int IsFull(PriorityQueue H)                     //如果数组的大小为最大值的话，数组满了
{
return H->Size == H->Capacity;
}