1.堆的概念
如果有一个关键码的集合K = { 在一个一维数组中，并满足： ，， = 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2.性质
3.逻辑结构和物理结构（存储结构）
4.堆的实现前提
4.1思路：
我们用数组用来实现堆。是因为堆是完全二叉树，数据是连续的，没有空数据。既然连续，那么下标之间的关系就可以很好的帮助我们找见父子节点的关系。
注：数组都可以看做是完全二叉树，但是不能都看做堆。因为堆的数据存放前后有大小要求。
4.2下标之间的关系
4.3建什么堆--大堆 / 小堆
5.堆的实现
怎样建堆---向上调整建堆 / 向下调整建堆
5.1向上调整建堆
5.1.1定义：
从根节点开始，找它的父亲，先入堆，再比较父子的大小关系，根据建 大/小 堆，判断父子是否需要交换，再判断下一个节点。再找它的父亲.......。一直将数据全部入堆之后，就完成向上调整建堆了
注1：从定义看，我们发现，向上调整建堆，就是将数据，从第一个开始，一个接一个入堆，之后再判断是否需要交换。
注2：每当插入一个新节点时，只会影响它绝对路径上的节点（也就是所有祖先节点）。为什么？
因为堆是从无到有的，每当插入一个新节点，插入之前的所有节点就已经是堆了，不需要调整。只需要调整当前新节点。
注3：插入数据之前，得保证之前的数据是一个堆，才可以用向上调整继续建堆。（注2解释了为什么插入之前的数据就已经是堆了）
思考：插入数据之前，得保证之前的数据是一个堆。为什么要这样？
维持堆的性质：如果插入数据之前的结构不是堆，那么在进行向上调整时，可能会导致错误的结果，因为向上调整算法依赖于堆的性质（即每个节点的值都大于或等于其子女节点的值，或者每个节点的值都小于或等于其子女节点的值）
5.1.2代码：
void Swap(HPDataType* a, HPDataType* b) {
HPDataType* tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustUp(HPDataType* a, HPDataType child) {
int parent = (child - 1) / 2;
while (child > 0) {
if (a[child] < a[parent]) {
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
int main() {
int a[6] = { 32,70,65,60,50,100 };
for (int i = 0; i < 6; i++) {
AdjustUp(a, i);
}
for (int i = 0; i < 6; i++) {
printf("%d ", a[i]);
}
return 0;
}
5.1.3代码解析：
我们最后一个节点，一直向上调整，如果没有父亲，那么就结束最后一次调整。例如下面这张图
想清楚，child和parent谁先到达根节点？child先到。那么此时child=0,parent=（0-1）/ 2 =0，while循环条件满足，就会造成死循环。
思考：为什么先改变 child 的值，先改 parent 的值不可以么？
也可以这样，那parent改之前的值得先存起来，parent改之后，将存起来的值赋值给child。或者是求改之后的parent的child的child。
综上所诉，先改child，再改parent。
5.2向下调整建堆
5.2.1定义：
跟向上调整一样，向下调整就是找孩子。
有三点区别：1.找哪一个孩子，左孩子还是右孩子？
2.从哪开始向上调整建堆是从根开始，向下调整可以从根开始么？不可以，因为根节点的左右子树不是堆。
3.顺序是从后往前。
注：向上调整建堆可以从根开始，本质是因为它是从根节点开始找父亲节点，然后父子之间判断是否需要交换。然后再找下一个节点。建堆的过程是从无到有的。但是向下调整是找孩子，又需要保证孩子的左右子树都是堆，这次调整才有意义。
注：左右子树都是堆，才可以用向下调整。（参考：向上调整的注3）。
5.2.2代码：
void Swap(HPDataType* a, HPDataType* b) {
HPDataType* tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustDown(HPDataType* a, int parent, int num) {
int child = parent * 2 + 1;
while (child <= num - 1) {
if (child + 1 < num) {
//右孩子存在
//用假设法，找见较大的那个孩子的下标
if (a[child + 1] > a[child]) {
child = child + 1;
}
}
//走到这一步，l_child就是较大值孩子的下标
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent=child;
child = child * 2 + 1;
}
else {
break;
}
}
}
int main() {
int a[6] = { 32,70,65,60,50,100 };
int num = sizeof(a) / sizeof(a[0]);
for (int i =(num-1-1)/2 ; i >=0; i--) {
AdjustDown(a, i, num);
}
for (int i = 0; i < 6; i++) {
printf("%d ", a[i]);
}
return 0;
}
5.2.3代码解析：
思考：为什么先动parent，后动child？
和向上调整一样。要么先存值，要么跳跃的找。
