目录
满二叉树：
完全二叉树：
堆是一种特殊的完全二叉树：
我们可以以数组的方式存储堆。
父节点和子节点下标关系的推导：
1.使用数学归纳法证明n2 + 1 = n0：
2.使用边和节点的关系证明n2 + 1 = n0：
我们来看看堆有哪些方法：
向下调整算法：
向上调整算法：
堆排序：
向下调整建堆：
向上调整建堆：
topk问题：
满二叉树：
定义：
一棵深度为 kk 的满二叉树，是指所有非叶子节点都有左右子节点，且所有叶子节点都在最底层的二叉树。换句话说，满二叉树的每一层都被完全填满。
完全二叉树：
定义：
一棵深度为 kk 的完全二叉树，除了最后一层外，其他层的节点都被完全填满，且最后一层的节点尽可能靠左排列。完全二叉树允许最后一层不满，但空缺只能出现在右侧。
堆是一种特殊的完全二叉树：
满足以下性质：
-
完全二叉树结构：堆的逻辑结构是一棵完全二叉树（所有层除最后一层外都被填满，且最后一层的节点尽可能靠左排列）。
-
堆序性质（Heap Property）：
-
最大堆（Max Heap）：每个节点的值 ≥ 其子节点的值（根节点是最大值）。
-
最小堆（Min Heap）：每个节点的值 ≤ 其子节点的值（根节点是最小值）。
-
当我们给完全二叉树的每个节点从上到下从左到右编个序号。
我们可以发现父节点和子节点的序号之间存在一些关系。
parent*2 + 1 = childleft(左子节点)
parent*2 + 2 = childright(右子节点）
(child-1)/2 = parent.(这是C语言的计算)
当我们知道父节点的下标，就能知道子节点的下标，知道子节点的下标也可以知道父节点的下标。
我们可以以数组的方式存储堆。
注意：
1.只有向下取整的计算规则（当x是小数时，取不大于x的最大整数）才能用数组的形式存储完全二叉树。
2.只有完全二叉树适合用数组来存储
父节点和子节点下标关系的推导：
证明这个关系我们用到了一个二叉树的结论：n2 + 1= n0：度为2的节点个数比度为0的节点个数少一个。
而这个结论也是可以证明的
1.使用数学归纳法证明n2 + 1 = n0：
由于第一个节点满足n2+1 = n0;
假设第k个节点也满足n2+1 = n0;
我们要证明第k+1个节点也满足n2 +1 = n0;
第k+1个节点有两种情况：
情况1：它是一个左子节点：那么度为0的父节点就变成了度为1的节点，同时多出一个度为0的子节点。（度为0的节点个数不变）
情况2：它是一个右子节点：那么度为1的父节点就变成了度为2的节点，同时多出一个度为0的子节点（度为0的节点个数和度为2的节点个数同时+1）。
2.使用边和节点的关系证明n2 + 1 = n0：
像下面这样一个二叉树，一共有6条边，n0+n1+n2-1（除了根节点外的每个节点都贡献一条边）
而边的个数同时也等于n2*2+n1（度为2的节点个数*2 + 度为1的节点个数）
列等式：n0+n1+n2-1 = n2*2+n1
化简得：n0 = n2+1
知道了堆可以用数组来存储，
我们来看看堆有哪些方法：
typedef int HPDataType;
typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);初始化和销毁不用说，其中基本的方法有插入、删除和取堆顶数据。以及堆的数据个数和堆的判空。
在插入数据或者删除数据的时候，为了保证数据始终是以堆的形式在存储，我们引出了向下调整算法和向上调整算法：
向下调整算法：
从一个根开始，父节点和左右子节点中较大的（或者较小的）那个比较，如果父节点小（或者大）就交换，否则就退出循环。
void AdjustDown(HPDataType* a, int n, int root)
{int parent = root;int child = parent * 2 + 1;while (child < n){//建大堆//找出左右孩子中比较大的那个if ((child + 1 < n) && (a[child] < a[child + 1])){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent * 2 + 1;}else {break;}}
}向上调整算法：
从一个子节点开始，和它的父节点比较，不符合堆的关系就交换，符合时退出循环。
在实际实现向上调整算法的时候循环判断很容易写错：
如果这里写成了parent >= 0就会导致程序死循环：当parent = 0时，child更新后为0，parent再更新还是为0.
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0)//这个判断条件很容易写错{if (a[parent] < a[child]){Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}堆排序：
堆排序的思想就是，对一个无序的数组，首先进行建堆（保证堆顶的数据是最大的或者最小的）。把堆顶的数据交换到堆尾，然后向下调整一遍。同时更新堆尾下标。
void HeapSort(int* a, int n)
{//向下调整建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//建好堆之后，交换堆顶和堆尾的数据，向下调整。int end = n - 1;//先创建一个变量记录排序到哪个位置了while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}
}
这里的建堆方式有两种：一种是向上调整建堆，另一种是向下调整建堆。我们可以分析一下这两种方式的时间复杂度。
完全二叉树向下调整建堆和向上调整建堆最好情况下，最后一层只有一个节点，最坏情况下最后一层是满的，由于我们要分析时间复杂度，所以要选择满二叉树来分析。
向下调整建堆：
从下到上，保证调整的时候只有根不是堆的关系。向下调整建堆可以从第一个非叶子节点开始。
向下调整建堆的时间复杂度是O(N)。
向上调整建堆：
从上到下，保证上层是堆的关系。
向上调整建堆的时间复杂度是N*logN
topk问题：
从n个元素中选出最大（最小）的k个元素。
先建堆，选最大元素建小堆（比榜尾大就入榜），选最小元素建大堆（比榜尾小就入榜）。
void CreateNDate()//创建N个数据的方法
{int n = 10000;FILE* fin = fopen("data.txt", "w");if (fin == NULL){perror("fopen fail");exit(1);}srand((unsigned int)time(NULL));for (int i = 0; i < n; i++){fprintf(fin, "%d\n", rand() % 100000 + 1);}fclose(fin);
}
void PrintTopK(int k)
{//入榜条件是比榜尾要大，所以要和榜尾比较int* topk = (int *)malloc(sizeof(int) * k);//打开文件读取数据FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen fail\n");exit(1);}int num = 0;//入k个数据for (int i = 0; i < k; i++){fscanf(fout, "%d", &num);topk[i] = num;}//向下调整建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(topk, k, i);}//循环判断数据是否入榜while (fscanf(fout, "%d", &num) != EOF){if (num > topk[0]){topk[0] = num;AdjustDown(topk, k, 0);}}fclose(fout);for (int i = 0; i < k; i++){printf("%d ", topk[i]);}
}
详解)
