什么是堆呢？堆其实就是数组，然后我们将数组看成树的结构，创建堆可以是大堆也可以是小堆，有堆就可以用来排序，与冒泡排序相比较效率高很多。
目录
堆的初始化
堆的插入操作
堆的删除操作
堆的销毁
堆的应用——堆排序
堆的初始化
堆就是数组，所以我们在创建结构体时，需要一个指针指向数组，以及数组容量和有效个数。
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;typedef int HPDatatype 改变int就可以轻易改变数组类型，不需要改多处。
初始化
void HeapInit(Heap* php)
{assert(php);php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);if (php->a == NULL){perror("malloc fail");return;}php->size = 0;php->capacity = 4;
}使用malloc函数申请一片空间，使结构体成员指针指向该空间，一开始给四个空间，后面需要容量不够就进行扩容。
堆的插入操作
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);if (hp->capacity == hp->size){HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * hp->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}hp->a = tmp;hp->capacity *= 2;}hp->a[hp->size] = x;hp->size++;//向上排Sortup(hp->a, hp->size-1);
}向堆插入数据，就是向一个数组插入数据，先对数组进行容量判断，如果有效个数等于容量就进行扩容，使用realloc函数进行扩容，向堆中插入数据之后我们需要进行向上调整，就是较大的数据向上调整，在数组中就是后面的数据向前排，树顶的数据要大于左右孩子的数据，这里我们的堆是小堆。
void Sortup(HPDataType* p, int child)
{int parent = (child - 1) / 2;while (child > 0){if (p[child] > p[parent]){Swap(&p[child], &p[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}向上调整函数，每当插入一个数据就需要进行调整，这里我们需要知道一个“父母”和“孩子”的关系
从这个图中可以看出左孩子child = parent*2，右孩子=parent*2+1，在向上调整中只需要知道子节点的位置就可以得到父母节点的位置，而插入数据都是在数组的尾部，所以只需要传最后一个数据的下标（树结构和数组一样从0开始），根据参数来算出父母节点，进行比较，如果子节点大于父母节点就进行交换，交换之后就让child等于parent，再计算新child的父母节点，反之退出循环。进行交换专门写一个函数：
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}交换函数传参不可以传值，因为形参是实参的一份临时拷贝，所以在这里需要传址调用。
堆的删除操作
堆的删除操作，应该怎么样删除数据呢？ 直接删除最后一个元素的话，最后一个元素不一定是最小的，但是第一个数据一定的最大的，所以我们删除第一个元素。那么又有一个问题，第一个元素可以直接删除吗？如果直接删除就需要将整个剩下数组往前挪，这样的话效率就太低了。
这里我们可以将第一个数据和最后一个数据进行交换，然后删除最后一个数据，最后来一个向下调整，就可以完成删除操作，并且效率比挪动数据高多了。
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(&hp));Swap(&hp->a[0], &hp->a[hp->size-1]);hp->size--;Sortdown(hp->a, 0, hp->size);
}向下调整函数需要三个参数，删除过后的数组，第一个数据的下标，有效数据个数。
void Sortdown(HPDataType* p, int parent, int n)
{int child = parent * 2 + 1;while ((parent * 2 + 1) < n){if (((child + 1) < n) && (p[child] < p[child + 1])){child++;}if (p[parent] < p[child]){Swap(&p[parent], &p[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}拿一组数据1,2,3,4,5,6,7 ，在堆中是以下结构
数组中：
根据删除操作，先交换第一个和最后一个数据，再删除。
接着进入向下调整函数，先对左右孩子进行大小比较，我们先假设左孩子更大，如果有右孩子并且右孩子比左孩子更大就child++，接着就parent和child进行比较，如果child更大就进行交换，反之退出循环
这样我们就完成了我们的删除操作， 效率比一个一个挪动数据快多了。
堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp->a);hp->a = NULL;hp->capacity = 0;hp->size = 0;
}释放申请的那片空间，结构体成员指针置空，容量和有效数据个数等于0。
堆的应用——堆排序
首先是先建堆，那么建大堆呢还是建小堆呢？这就看是排升序还是排降序。
升序：建大堆
降序：建小堆
建堆的时间复杂度为O(n)。
使用向下调整思想就可以实现堆排序
void HeapSort(int* a, int n)
{//向下建大堆---最大的数据在顶for (int i = (n-2)/2; i >= 0; i--){Sortdown(a, i, n);}//向上建大堆/*for (int i = 0; i < n; i++){Sortup(a, i);}*/int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);end--;Sortdown(a, 0, end);}
}
test()
{int a[12] = { 8,7,6,3,5,4,9,1,2,0,8,9 };HeapSort(a,12);for (int i = 0; i < 12; i++){printf("%d ", a[i]);}
}建堆有两种方法，一个是向下建堆，一个是向上建堆，在数据很多时向下建堆比向上建堆更快一些 ，反之向上建堆更快。交换第一个和最后一个，再向下调整，这里和堆删除操作差不多。
运行结果：
