1.堆的基本结构
数据结构的堆和我们在操作系统里的堆不同，我们要讲的堆就是数据结构的堆。
堆的逻辑结构（完全二叉树）和物理结构（数组）
这里的堆是一个小根堆，（堆只分为大根堆和小根堆）
ps:小根堆： 堆的逻辑结构（完全二叉树中）的任意一个结点值必须大于他的左孩子和右孩子的结点值,大根堆同理。
值得注意的是这里即使是小根堆但依然不是有序的，通过小根堆我们能直接获取到的是最小值。
PS：大小堆都只是父子之间的大小关系，兄弟之间是没有大小关系的
所以下面让我们看看如何对堆进行排序。
堆只有大根堆和小跟堆，
2.堆的插入删除
堆的核心就是插入数据和删除数据
2-1用数组下标计算父子关系：
leftchild=2*parent+1;
rightchild=2*parent+2;
parent=(child-1)/2;
我用下图理解了上面的child不分leftchild和rightchild的原因。（看不懂可以按自己的方式理解）
2-2堆上插入元素-向上调整算法
如果在小根堆上插入一个数据，由于堆的物理结构是数组，我们采用顺序表实现，同时，如果只是简单的在数组的最后面插入一个数据，这是相当简单的，但是我们为了在插入新数据后能够继续保持堆的形态，我们通常在插入一个新数据后采用向上调整算法来实现。
向上调整法使用前提：树本身就是大堆或者小堆
时间复杂度：LogN
纠正上图：应该是向上调整算法，下图是向上调整法的图解实现
你是否有一个问题就是为什么在将12向上调整的时候，只用关心12的祖先的大小关系
在换的过程中不会打乱除了祖先外的结点和祖先结点的大小关系吗？
答案：不会，因为这本来就是小根堆，如果某结点要下移来交换，移下来的结点换下来之后一定比最原先在换下来的那个位置的结点值还更小，所以一定能够保证换下来之后不会造成父子关系乱掉。
那么向上调整法的代码实现是什么样的呐？如下
typedef struct Heap { int* a; int size; int capacity; }HP; void AdjustUp(int* a, int child) { assert(a); int parent = (child - 1) / 2; while (child > 0)//循环里写的是继续的条件while(满足):child==0时跳出循环 { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } //插入X后继续保持堆形态 void HeapPush(HP* php, int x) { assert(php); if (php->size == php->capacity) { int newcapacity = 2 * php->capacity; int* temp = (int*)realloc(php->a, sizeof(int) * newcapacity); if (temp == NULL) { perror("realloc fail.\n"); exit(-1); } php->a = temp; php->capacity = newcapacity; } php->a[php->size] = x; php->size++; //向上调整算法，传要调整的数组和从哪个下标child开始调 AdjustUp(php->a, php->size - 1); }
HeapPush函数的内容和原来顺序表不同的是在插入新数据X后进行了向上调整，因此我们的关注点只需放在AdjustUp函数。
int main() { int a[] = { 10,2,20,4,12,67,56,1 }; int size = sizeof(a) / sizeof(a[0]); HP heap; HeapInit(&heap); for (int i = 0; i < size; i++) { HeapPush(&heap, a[i]); } HeapPrint(&heap); HeapDestory(&heap); return 0; }
测试用例：10,2,20,4,12,67,56,1
写成完全二叉树的形式：（预期结果：小根堆）
结果：小根堆，代码无误~~
要是我想得到大根堆改如何改呐？
小根堆就是要把小的换上去
大根堆就是要把大的换上去
因此同样顺序表插入代码，只需在调整部分稍作修改
也就是只需改一下调整部分代码的判断条件
2-3删除堆顶元素-向下调整算法
错误的顺序表式删除头：
正确的删除堆顶元素方式：向下调整算法
前提：堆顶的把左子树和右子树都是大堆或者小堆。
向下调整算法：将要删除的堆顶元素和数组的最后一个元素先做一个交换，交换后覆盖删除数组的最后一个元素，，将堆顶元素做一次向下调整。
void HeapAdjustDown(int* a, int n, int parent) { int minchild = 2 * parent + 1; while (minchild < n) { if (minchild + 1 < n && a[minchild] > a[minchild + 1]) { minchild++; } if (a[minchild] < a[parent]) { Swap(&a[minchild], &a[parent]); parent = minchild; minchild = 2 * parent + 1; } else { break; } } } //删除堆顶元素，找到次小或次大的元素 //删除之后仍要尽量保持堆的形态 void HeapPop(HP* php) { assert(php); Swap(&php->a[0], &php->a[php->size - 1]); php->size--; HeapAdjustDown(php->a, php->size-1,0); }
