数据结构学习之堆

本篇我们将学习新的数据结构——二叉树。

作者的个人gitee：楼田莉子 (riko-lou-tian) - Gitee.com

树的概念

树形结构

非树形结构

树的相关术语

树的表示

树在实际生活上的应用

二叉树

慢二叉树

完全二叉树

二叉树的储存结构

二叉树的存储结构

顺序结构

链式结构

堆的概念（顺序结构二叉树）

堆的模拟实现

堆的结构

堆的初始化

堆的销毁

堆的打印

判断堆是否为空

堆的数据插入

交换函数

堆向上调整

堆向下调整

数据删除

堆排序

堆的Top-k问题

树的概念

树是一种非线性的数据结构。它由n(n>=0)个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。

树形结构

有⼀个特殊的结点，称为根结点，根结点没有前驱结点

除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

具体表现如下：

树形结构中，⼦树之间不能有交集，否则就不是树形结构
当然实际上也存在非树形结构。

非树形结构

如下图所示，就是几个非树形结构。

⼦树是不相交的（如果存在相交就是图）

除了根结点外，每个结点有且仅有⼀个⽗结点

⼀棵N个结点的树有N-1条边

树的相关术语

⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图：A是B的⽗结点

⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图：B是A的孩⼦结点结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0

树的度：⼀棵树中，最⼤的结点的度称为树的度；如上图：树的度为 6

叶⼦结点/终端结点：度为 0 的结点称为叶结点；如上图： B、C、H、I... 等结点为叶结点分⽀结点/⾮终端结点：度不为 0 的结点；如上图： D、E、F、G... 等结点为分⽀结点兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)；如上图： B、C 是兄弟结点

结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；树的⾼度或深度：树中结点的最⼤层次；如上图：树的⾼度为 4

结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先

路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙

森林：由 m（m>0）棵互不相交的树的集合称为森林；

树的表示

孩⼦兄弟表⽰法：

树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法

struct TreeNode
{
struct Node* child; // 左边开始的第⼀个孩⼦结点
struct Node* brother; // 指向其右边的下⼀个兄弟结点
int data; // 结点中的数据域
}

由上述代码，可以这么推广

树在实际生活上的应用

⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

二叉树

而树型结构中，我们常用的是二叉树。一棵二叉树是结点的有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

我们可以发现：

1. ⼆叉树不存在度⼤于 2 的结点

2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

注意：对于任意的⼆叉树都是由以下⼏种情况复合⽽成的

二叉树也有特殊和普通两种情况。

我们先学习特殊情况。

慢二叉树

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是 2k - 1 ，则它就是满⼆叉树。

观察发现满二叉树每一层有2^（n-1）个结点，则总结点数目就是2^n-1个（运用等比数列的求和公式）

完全二叉树

完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树

完全二叉树的特点：

（1）除了最后一层，每层节点个数达到最大。

（2）最后一层的节点个数不一定达到最大。（最后一层达到最大则既是完全二叉树也是满二叉树）

（3）结点从左到右依次排列。

满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

⼆叉树性质

根据满⼆叉树的特点可知：

1、若规定根结点的层数为 1 ，则⼀棵⾮空⼆叉树的第i层上最多有 2i-1 个结点

2、若规定根结点的层数为 1 ，则深度为 h 的⼆叉树的最⼤结点数是 2h - 1

3、若规定根结点的层数为 1 ，具有 n 个结点的满⼆叉树的深度h= $\log 2 (n+1)$ ( log以2为底， n+1 为对数)

二叉树的储存结构

二叉树的存储结构

⼆叉树⼀般可以使⽤两种结构存储，⼀种顺序结构，⼀种链式结构

顺序结构

顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，完全⼆叉树更适合使⽤顺序结构存储。

其中非完全二叉树的空数组表示NULL。

现实中我们通常把堆（⼀种⼆叉树）使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。

链式结构

⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。后期我们学到⾼阶数据结构的时候如红⿊树等会⽤到三叉链。

堆的概念（顺序结构二叉树）

堆是一种特殊的二叉树，除了二叉树的性质之外还有其他的性质

如果有⼀个关键码的集合 K = {k0 , k1 , k2 , ...，kn-1 }，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： Ki <= K2∗i+1（Ki >= K2∗i+1 且Ki <= K2∗i+2），
i = 0、1、2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

堆分为两类：

大根堆：

小根堆：

但是小堆≠升序，大堆≠降序。

堆具有以下性质：

堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；

堆总是⼀棵完全⼆叉树。

⼆叉树性质：

对于具有 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 否则⽆右孩⼦。

堆的模拟实现

堆的结构

typedef int HPDataType;
//堆的结构
typedef struct Heap
{HPDataType*arr;	//堆中的数据int size;		//堆的有效数据个数int capacity;	//堆的总容量
}HP;

堆的初始化

//堆的初始化
void HP_Init(HP* php)
{php->arr = NULL;php->size=php->capacity  = 0;
}

堆的销毁

//堆的销毁
void HP_Destroy(HP* php)
{if(php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

堆的打印

void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}

判断堆是否为空

//判空
bool HP_Empty(HP* php)
{assert(php);return php->size == 0;
}

堆的数据插入

初始版本：

//堆的插入操作
void HP_Push(HP* php, HPDataType data)
{assert(php->arr!= NULL);if (php->size == php->capacity){int new_capacity =php->capacity==0?4: (php->capacity) * 2;HPDataType*tmp=(HPDataType*)realloc(php->arr, new_capacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc error");exit(1);}php->arr = tmp;php->capacity = new_capacity;}php->arr[php->size++] = data;
}

但是记住，数据插入后要进行调整让它还是一个堆。

所以我们还需要一个堆向上调整的函数

因此最终版本的数据插入函数

//堆的插入操作
void HP_Push(HP* php, HPDataType data)
{assert(php);//判断空间是否足够if (php->size == php->capacity){int newCapcity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapcity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapcity;}php->arr[php->size] = data;//向上调整HP_UpAdjust(php->arr, php->size);++php->size;
}

交换函数

void swap(HPDataType* x, HPDataType* y)
{HPDataType tmp = *x;*x = *y;*y = tmp;
}

堆向上调整

//堆在进行插入的时候需要调整为堆
//堆数据向上调整
void HP_UpAdjust(HPDataType* php, int child)
{int parent = (child - 1) / 2;while (child > 0){//大堆：>//小堆：<if (php[child] > php[parent]){//调整swap(&php[child], &php[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}}

堆向下调整

//堆数据向下调整
void HP_DownAdjust(HPDataType* php, int parent,int n)
{int child =parent * 2 + 1;//左孩子while (child < n){//大堆：<//小堆：>if (child+1<n && php[child] < php[child + 1]){child++;}//大堆：>//小堆：<if (php[child] > php[parent]){//调整swap(&php[child], &php[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

child循环了多少次取决于堆的高度/深度

数据删除

//堆的删除操作
HPDataType HP_Pop(HP* php)
{assert(!HP_Empty(php));swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//向下调整HP_DownAdjust(php->arr, 0, php->size);
}

堆排序

当我们写出下面这行代码的时候

void test2()
{HP hp;HP_Init(&hp);HP_Push(&hp, 27);HP_Push(&hp, 58);HP_Push(&hp, 10);HP_Push(&hp, 34);HPPrint(&hp);while (!HP_Empty(&hp)){int top=HP_Top(&hp);printf("%d ", top);HP_Pop(&hp);}HP_Destroy(&hp);
}

运行一下结果为：

这就是堆排序吗？

并不是。

在堆里堆顶一定是最值。大堆堆顶是最大值，小堆堆顶是最小值

堆的排序是利用堆的思想而不是利用堆的数据结构

在实际的堆排序中不可以用堆的数据结构来实现，最好用向下排序算法来构建堆的数据结构

代码如下：

向下调整算法的建堆：

//堆的堆排序操作
void HP_Sort(int* arr, int n)
{//建造堆——通过向下调整算法//n-1是最后一个子结点的下标，i表示的最后一个的父结点的下标for (int i =(n-1-1)/2; i >= 0; i--){HP_DownAdjust(arr, i, n);}//堆排序int end = n - 1;while (end > 0){//交换堆顶和最后一个元素swap(&arr[0], &arr[end]);//向下调整HP_DownAdjust(arr, 0, end);--end;}
}

测试代码：

void print(int *a,int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}
}
void test3()
{int a[] = { 58, 34, 27, 10, 91, 43, 61, 80, 12 };print(a,sizeof(a)/sizeof(a[0]));printf("\n");printf("排序后：\n");HP_Sort(a, 9);print(a, sizeof(a) / sizeof(a[0]));printf("\n");}

向上调整算法建堆：

//堆的堆排序操作
void HP_Sort(int* arr, int n)
{//建造堆——通过向下调整算法//n-1是最后一个子结点的下标，i表示的最后一个的父结点的下标/*for (int i =(n-1-1)/2; i >= 0; i--){HP_DownAdjust(arr, i, n);}*///建堆——通过向上调整算法for (int i = 0;i < n;i++){HP_UpAdjust(arr, i, n);}//堆排序int end = n - 1;while (end > 0){//交换堆顶和最后一个元素swap(&arr[0], &arr[end]);//向下调整HP_DownAdjust(arr, 0, end);--end;}
}

那么这两者的时间复杂度有什么区别呢？

为了方便推理，我们使用满二叉树。因为堆是完全⼆叉树，⽽满⼆叉树也是完全⼆叉树，此处为了简化使⽤满⼆叉树来证明(时间复杂度本来看的就是近似值，多⼏个结点不影响最终结果)

如下图所示，

每一层有2^（n-1）个结点，需要向上移动n-1次，则需要移动结点总的移动步数为：每层结点个数 * 向上调整次数（第⼀层调整次数为0）

利用数列相关的求和知识可得：

由上可知，向上调整复杂度为O（N）

堆的Top-k问题

TOP-K问题：即求数据结合中前K个最⼤的元素或者最⼩的元素，⼀般情况下数据量都⽐较⼤。

⽐如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。

对于Top-K问题，能想到的最简单直接的⽅式就是排序，但是：如果数据量⾮常⼤，排序就不太可取了

(可能数据都不能⼀下⼦全部加载到内存中)。最佳的⽅式就是⽤堆来解决，基本思路如下：

1）⽤数据集合中前K个元素来建堆

前k个最⼤的元素，则建⼩堆

前k个最⼩的元素，则建⼤堆

2）⽤剩余的N-K个元素依次与堆顶元素来⽐较，不满⾜则替换堆顶元素将剩余N-K个元素依次与堆顶元素⽐完之后，堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素。

//top-k问题
//先建立一个数据
void createData()
{//创建数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fp = fopen(file, "w");if (fp == NULL){printf("文件打开失败！\n");return;}for (int i = 0; i < n; i++){int num = rand() % 10000;fprintf(fp, "%d\n", num);}fclose(fp);
}
void top_k()
{int k = 0;printf("请输入k:>");scanf("%d", &k); const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;};int val = 0;int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 建k个数据的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){HP_DownAdjust(minheap, k, i);}// 遍历剩下的n-k个数据int x = 0;while (fscanf(fout, "%d", &x) != EOF){// 如果当前值比堆顶大，替换堆顶并调整if (x > minheap[0]){minheap[0] = x;HP_DownAdjust(minheap, 0, k); }}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}printf("\n");//free(minheap); // 添加内存释放fclose(fout);
}
//读取数据
int main()
{top_k();return 0;
}

时间复杂度分析：