作者：一个喜欢猫咪的的程序员
专栏：《数据结构》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
堆的概念及结构：
如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
- 父节点都比其的子节点大的完全二叉树叫做大堆。
- 父节点都比其的子节点小的完全二叉树叫做小堆。
堆的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
堆的实现思路：（我们以大堆为例）
需要实现的接口：
void Swap(HPDataType* p1, HPDataType* p2); void HeapCreate(HP* php, HPDataType* a, int n); void HeapPrintf(HP* php); void HeapInit(HP* php); void HeapDestroy(HP* php); void HeapPush(HP* php, HPDataType x); void HeapPop(HP* php); HPDataType HeapTop(HP* php); int HeapSize(HP* hp); bool HeapEmpty(HP* hp); void Ajustdown(HPDataType* a, int n, int parent); void Ajustup(HPDataType* a, int n);
从堆的结构中，我们了解到堆是一个数组a，并且后续我们可能需要对数组进行扩容和缩小，因此我们还需要两个变量：有效长度size和容量capacity
实现的一些细节：
HeapInit、HeapDestroy、HeapPrintf函数没有什么好说的。
void HeapInit(HP* php) { assert(php); php->capacity = 0; php->size = 0; php->a = NULL; } void HeapDestroy(HP* php) { assert(php); assert(php->a); free(php->a); free(php); } void HeapPrintf(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); }
HeapPush函数：
因为我们的存储结构是一个数组，Push就直接添加数据吗？
当capacity==size时扩容一下（包括初始化的方案），当size==0时，扩容4个空间，否则扩容二倍的空间，capacity也跟着扩大，当push后size++。
以大堆为例：
100比30大，30和100需要调换位置，然后100又比70大，70和100需要再次调换位置。
我们添加的数据x作为子节点child，child可能会比它的父节点parent大。因此需要将child向上调整Ajustup。
void HeapPush(HP* php, HPDataType x) { assert(php); if (php->size == php->capacity) { int newcapacity=php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp=(HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity); if (tmp == NULL) { perror("realloc fail"); exit(-1); } php->a = tmp; php->capacity = newcapacity; } php->a[php->size++] = x; Ajustup(php->a, php->size-1); }
