目录
1 – 1 · 树的概念
1 – 2 · 树的基本术语
1 – 3 · 树的表示
1 – 4 · 树形结构应用场景
2 · 二叉树
2 – 1 · 二叉树的概念
2 – 2 · 特殊的二叉树
2 – 3 · 二叉树的性质
3 · 堆
3 – 1 · 堆的概念
3 – 2 · 堆的存储结构
3 – 3 · 堆的实现
3 – 3 – 1 · 初始化
3 – 3 – 2 · 销毁
3 – 3 – 3 · 向上调整
3 – 3 – 4 · 插入
3 – 3 – 5 · 向下调整
3 – 3 – 6 · 删除
4 · 堆排序
4 – 1 · 建堆的选择
4 – 2 · 代码实现
4 – 3 · 测试一下
5 · Top-K 问题
5 – 1 · 生成随机数
5 – 2 · 代码实现
5 – 3 · 测试一下
总结
在了解堆之前，我们需要先了解一些关于树和二叉树的知识。
1 – 1 · 树的概念
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。
把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根在上，而枝干和叶在下的。
比如下面这张图就是树：
其中有一个特殊的结点，它没有前驱结点，它是根节点
除去根节点，其余结点被分为多个不相交的集合，一个集合内又是类似于树的结构的子树，一颗子树的根只有一个前驱结点，但是可以有多个后继结点，因此，树是递归定义的。
对于一棵树：
1. 子树是不相交的
2. 除去根结点，每个结点有且只有一个双亲结点
3. 对于一颗有N个结点的树，它的边数为 N-1
1 – 2 · 树的基本术语
如下：
结点：树的结点包含一个数据元素及若干指向其子树的分支。
结点的度：一个结点含有的子树(或后继结点)的个数称为该结点的度
树的度：一棵树中，最大的结点的度称为树的度
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的高度或深度：树中结点的最大层次
叶子结点或终端结点：度为0的结点称为叶子结点
分支结点或非终端结点：度不为0的结点
双亲结点：若一个结点含有孩子结点，则这个结点称为其孩子结点的双亲结点
孩子结点：一个结点 含有的子树的根结点(后继结点) 称为该结点的孩子结点
兄弟结点：具有相同双亲结点的结点互称为兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟
结点的祖先：从根到该结点所经分支上的所有结点
子孙：以某结点为根的子树中任一结点都称为该结点的子孙
森林：由m（m>0）棵互不相交的树的集合称为森林；
1 – 3 · 树的表示
树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，
实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等
我们简单介绍一下孩子兄弟表示法：
typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
对上面这棵树，我们可以这样来表示：
1 – 4 · 树形结构应用场景
文件系统是计算机存储和管理文件的⼀种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中，树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。
比如电脑磁盘和其中的文件。
2 · 二叉树
2 – 1 · 二叉树的概念
树形结构中，常用的是二叉树。
二叉树由一个有限结点集合组成，该集合由⼀个根结点加上两棵别称为左子树和右子树的⼆叉树组成或者为空。
简单来说，二叉树是一颗 最大度为2(可以小于2)的树。
上面就是一颗二叉树。
二叉树具有以下特点：
1. ⼆叉树不存在度大于 2 的结点
2. ⼆叉树的子树有左右之分，次序不能颠倒，因此⼆叉树是有序树
2 – 2 · 特殊的二叉树
1. 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 2^k – 1
则它就是满二叉树。
2. 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
要注意的是满二叉树是一种特殊的完全二叉树。
方便理解，我们看一张图：
2 – 3 · 二叉树的性质
1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2 ^ (i-1) 个结点.
2. 若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 2^h – 1
3. 对任何一棵二叉树, 如果度为0结点个数为a, 度为2的结点个数为c ,则有 a＝ c＋1
可以用 总结点个数 来证明：通过度计算总结点个数和通过结点之和来计算总结点个数
4. 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)
(是log以2为底，n+1为对数)
5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有结点从0开始编号，则对于序号为 i 的结点有：
1. 若i>0，i位置结点的双亲序号：(i-1) / 2 ；i=0，i 为根结点编号，无双亲结点
2. 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子
3. 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子
3 · 堆
3 – 1 · 堆的概念
堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。
需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
简单来说：
1. 堆中某个结点的值总是不大于或不小于其双亲结点的值；
如果所有双亲结点大于它的孩子结点，那么此时就是大堆；如果所有双亲结点小于它的孩子结点，那么此时就是小堆。
2. 堆总是一棵完全二叉树。
3 – 2 · 堆的存储结构
二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。
顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。
链式结构我们在下一篇会介绍。
既然堆是一颗完全二叉树，我们就使用顺序存储。
如下：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;//堆内元素个数
int _capacity;//堆容量
}Heap;
3 – 3 · 堆的实现
3 – 3 – 1 · 初始化
代码如下：
void HeapInit(Heap* ph)
{
assert(ph);
ph->_a = NULL;
ph->_capacity = ph->_size = 0;
}
3 – 3 – 2 · 销毁
代码如下：
void HeapDestroy(Heap* ph)
{
assert(ph);
free(ph->_a);
ph->_a = NULL;
ph->_capacity = ph->_size = 0;
}
3 – 3 – 3 · 向上调整
代码如下：
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUp(HPDataType* a, int child)
{
assert(a);
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;
}
}
}
我们插入数据，但是我们不能够确保插入之后，整体仍保持是堆。
因此我们写了向上调整
从给定的孩子结点(下标)开始，和自己的双亲结点比较
如果是建小堆，那么当 双亲结点 大于 孩子结点 时，就交换，
建大堆则是当 双亲 小于 孩子 就交换，
持续比较，直到与根节点比较完毕或不满足交换条件。
这样当我们插入新数据，再进行调整，就能让整体保持是堆。
3 – 3 – 4 · 插入
代码如下：
void HeapPush(Heap* ph, HPDataType x)
{
assert(ph);
//判满，满了就扩容
if (ph->_size == ph->_capacity)
{
int newcapacity = ph->_capacity == 0 ? 4 : ph->_capacity * 2;
HPDataType* ptr = (HPDataType*)realloc(ph->_a, newcapacity * sizeof(HPDataType));
if (ptr == NULL)
{
perror("realloc");
exit(1);
}
ph->_a = ptr;
ph->_capacity = newcapacity;
}
//在末尾插入
ph->_a[ph->_size] = x;
//向上调整
AdjustUp(ph->_a, ph->_size);
++ph->_size;
}
先判断堆是否满，随后进行尾插，再向上调整。
这里 ++size 和向上调整的顺序可以有变化，如果先 ++size ，那么调用向上调整的时候第二个参数就要传 ph->_size – 1。
3 – 3 – 5 · 向下调整
代码如下：
void AdjustDown(HPDataType* a, int size, int parent)
{
assert(a);
int child = parent * 2 + 1;
while(child < size)
{
//建小堆，找出左右孩子中小的那个
if (child + 1 < size && a[child + 1] < a[child])
{
child++;
}
//调整
if (a[child] < a[parent])
{
Swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
需要左右子树都为大堆或小堆
从给定的双亲结点(下标)开始，与自己的左孩子结点和右孩子结点比较
如果是建小堆，当 双亲结点 大于 孩子结点中的较小者 ，就和 较小的孩子结点 交换
建大堆则是当 双亲结点 小于 孩子结点中的较大者 ，与 较大的孩子结点 交换
持续比较，直到与叶子结点比较完毕 或 不满足交换条件。
也是一种保持堆的调整方式。
3 – 3 – 6 · 删除
代码如下：
void HeapPop(Heap* ph)
{
assert(ph);
//不能为空
assert(ph->_size > 0);
//先首尾交换
Swap(&ph->_a[0], &ph->_a[ph->_size – 1]);
//尾删
–ph->_size;
//向下调整
AdjustDown(ph->_a, ph->_size, 0);
}
顺序结构尾删很轻松，但是对于堆，尾删没有意义，堆的堆顶是整个堆中的最大值或最小值(根据大堆和小堆)。
因此对于堆的删除，我们删除的是堆顶。
但是直接头删，将后面的数据前移，会导致混乱，破坏整体结构。
所以我们先首尾交换，再尾删，这样就保持住了 堆顶的左右子树 仍为堆，再进行向下调整。
4 · 堆排序
堆排序，就是使用建堆和堆删除的思想来进行排序
想要排升序，就建大堆
想要排降序，就建小堆
然后首尾交换，将换到尾的数据视为排序完成，之后不再管，持续循环这样的操作，直到除堆顶数据，其余数据都排序完成，此时堆顶也就完成排序了，总体也排序完成了。
4 – 1 · 建堆的选择
我们有两种建堆方式，向上调整建堆 和 向下调整建堆，两种建堆方式有没有什么差异呢？
我们计算一下这两种方式的时间复杂度：
对向上调整建堆，假设高度为 h ，最坏的情况是 每一层的所有数据 调整 当前层数-1 次。
列成式子就是
这是一个差比数列，可以用待定系数法或错位相减法，可以得出：
高度和元素个数 n 是有关系的，h = log2(n+1) (以2为底，n+1的对数)
将h带回式子，再用大O渐进表示法，最后得出时间复杂度是 O(n*logn)
对向下调整建堆，我们从最后一个非叶子结点开始调整，因此是从 h-1 层开始调整的
同样假设高度为 h ，最坏情况是 每一层的所有数据 调整 h – 当前层数 次。
列成式子就是
同样是个差比数列，可以得出：
根据 h 和 元素总数 n 的关系，带回式子，再用大O渐进表示法，最后得出时间复杂度是 O(n)。
因此，我们选择使用向下调整建堆。
4 – 2 · 代码实现
代码如下：
void HeapSort(HPDataType* a, int size)
{
assert(a);
//建堆
//要排升序建大堆
//要排降序建小堆
//向上调整建堆
//for (int i = 0; i < size; i++)
//{
//AdjustUp(a, i);
//}
//向下调整建堆
//从最后一个非叶子结点开始向下调整
for (int i = (size – 1 – 1) / 2; i >= 0; i–)
{
AdjustDown(a, size, i);
}
int end = size – 1;
while (end > 0)
{
//先首尾交换
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
–end;
}
}
对于排序的时间复杂度，我们先首尾交换，然后向下调整，那么最坏情况就是 每一层的每个元素 调整 当前层数-1 次，与向上调整建堆类似，时间复杂度也是 O(n * logn)
那么对于堆排序整体，向下调整建堆的时间复杂度是 O(n) ，排序的时间复杂度是 O(n * logn)，总体的时间复杂度就是 O(n * logn)。
4 – 3 · 测试一下
我们测试一下堆排序：
void Test2()
{
int a2[] = { 4,8,9,3,7,1,6,2,0,5 };
int sz = sizeof(a2) / sizeof(int);
HeapSort(a2, sz);
for (int i = 0; i < sz; i++)
{
printf("%d ", a2[i]);
}
}
运行一下：
这里是建小堆排降序
5 · Top-K 问题
Top-K问题：即求数据结合中前K个最大的元素或者最小的元素，⼀般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于 Top-K 问题，最简单想到的方法就是用排序，但是如果数据量特别特别大，正常排序可能就不行了(可能数据都不能⼀下子全部加载到内存中)。这时可以用堆来解决：
先建一个大小为K的堆，如果找最大K个就建小堆，如果找最小K个就建大堆。
后面的 N-K 个元素依次与堆顶比较，如果建的是小堆，比堆顶元素大就替换，随后向下调整，如果建的是大堆，比堆顶元素小就替换，随后向下调整，元素比较完毕之后，堆内剩下的元素就是我们想要的。
5 – 1 · 生成随机数
代码如下：
void CreateData()
{
srand((unsigned int)time(NULL));
int n = 100000;
FILE* pf = fopen("data.txt", "w");
if (pf == NULL)
{
perror("fopen");
exit(1);
}
for (int i = 0; i < n; i++)
{
//减少重复，+i
//int data = rand() + i;
//方便判断
int data = (rand() + i) % 100000;
fprintf(pf, "%d\\n",data);
}
fclose(pf);
}
生成随机数到文件中，由于rand 生成的随机数范围有限，0到32767，因此我们再加上一个会变化的 i 。
5 – 2 · 代码实现
代码如下：
void TopK()
{
int k = 0;
printf("请输入k:>");
scanf("%d", &k);
//建k个元素的堆
//找最大k个建小堆
//找最小k个建大堆
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc");
exit(1);
}
FILE* pf = fopen("data.txt", "r");
if (pf == NULL)
{
perror("fopen");
exit(1);
}
//建堆
for (int i = 0; i < k; i++)
{
fscanf(pf, "%d", &minHeap[i]);
}
for (int i = (k – 1 – 1) / 2; i >= 0; i–)
{
AdjustDown(minHeap, k, i);
}
//后面 n-k 个与堆顶依次比较
int val = 0;
while (fscanf(pf, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjustDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minHeap[i]);
}
fclose(pf);
}
对于我们上面写的 TopK函数的时间复杂度，首先我们向下调整建堆，最坏情况下，后面的 N-K 个元素每个都要调整 我们建的堆的高度-1 次
因此，时间复杂度为 O(k + (n-k)logk)
5 – 3 · 测试一下
代码如下：
void Test3()
{
//CreateData();
TopK();
}
想要检查自己写的是否正确，可以对生成的随机数进行取模，让生成的随机数在一个已知的范围，然后手动修改文件中的数据，自己造出 K 个自己想要的值。
这里我们限制了生成的随机数在 100000以内，然后手动改了10个数
运行一下：
如果输入11，运行一下：
总结
以上简单介绍了堆有关内容，关于数据结构其余内容，请期待后续更新。
以上内容如有错误或不准确之处，欢迎指出，或者你有更好的想法，也欢迎交流。
