深入理解二叉树与堆：结构、实现与典型应用

云泽808

发布于 2025-12-30 18:11:22

1900

前言

大家好啊，我是云泽Q，一名热爱计算机技术的在校大学生。近几年人工智能技术飞速发展，为了帮助大家更好地抓住这波浪潮，在开始正文之前，我想先为大家推荐一个非常优质的人工智能学习网站）。它提供了从基础到前沿的系列课程和实战项目，非常适合想要系统入门和提升AI技术的朋友，相信能对你的学习之路有所帮助。

一、树

1.1 树的概念与结构

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

有一个特殊的结点，称为根结点，根结点没有前驱节点
除根结点外，其余结点被分成M（M>0）个互不相交的集合T1、T2、…、Tm，其中每一个集合Ti（1=<i<=m）又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。

树型结构中，子树之间不能有交集，否则就不是树形结构非树形结构：

子树是不相交的（如果存在相交就是图了，这部分涉及考研408的内容，后面我会抽时间单独来写）
除了根结点外，每个结点有且仅有一个父结点
一棵N个结点的树有N-1条边

1.2 树相关术语

父结点/双亲结点：若一个结点含有子结点，则这个结点称为其子结点的父结点；如上图：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）棵互不相交的树的集合称为森林；

1.3 树的表示

由于树是由一个一个结点组成，所以定义树的结构就是在定义结点的结构，且一个结点有多个指向孩子结点的指针

所以树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既要保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方法如：双亲表示法，孩子表示法、孩子双清表示法以及孩子兄弟表示法等，我这里只写一种最常用的孩子兄弟表示法

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

1.4 树形结构实际运用场景

文件系统是计算机存储和管理文件的一种方式，它利用树形结构来组织和管理文件和文件夹。在文件系统中树结构被广泛应用，它通过父结点和子结点之间的关系来表示不同层级的文件和文件夹之间的关联。

二、二叉树

2.1 概念与结构

在树形结构中，最常用的就是二叉树，一棵二叉树是结点的一个有限集合，该集合由一个根结点加上两棵分别称为左子树和右子树的二叉树组成或者为空

二叉树具有以下特点：

二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

注意：对于任意的二叉树都是由以下几种情况复合而成的

现时中的二叉树

2.2 特殊的二叉树

2.2.1 满二叉树

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

2.2.2 完全二叉树

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为k的，有n个结点的二叉树，除了最后一层，其他每层节点个数都达到最大，最后一层结点个数不一定达到最大（满二叉树就是完全二叉树的一种），还有完全二叉树的结点是从左到右依次排列的

二叉树性质

若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2i-1个结点
若规定根结点的层数为1，则深度为h的二叉树的最大结点数是2h-1
若规定根结点的层数为1，具有n个结点的满二叉树的深度h=log(n+1)（log以2为底，n+1为对数）

2.3 二叉树存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构

2.3.1 顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树就会有空间的浪费，完全二叉树更适合使用顺序结构存储

这是一棵满二叉树用数组来存储完全二叉树是把数据存储到数组当中。数据有对应的下标，按数组的下标，对每一个结点进行编号，把结点依次存储到数组当中

这就是一棵普通的二叉树，如果使用数组来存储的话，依旧对每个结点进行了编号，没有的结点和叶子也进行了编号，且不存在的结点用灰色的画，一共10个结点存储到数组当中就要申请大小为10的空间，这里就有了空间的浪费

这里如果没有的结点就不进行存储的话，就会破坏二叉树的原有结构因为这棵二叉树是根据数组画出来的，下标为0，一定是根结点，第二个值一定是A的左孩子，第3个一定是A的右孩子，下标为3一定是B的左孩子，如果为空的结点不进行存储的话，二叉树的父子关系就会被破坏

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

2.3.2 链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成（在结点的结构中有三个成员），数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。链式结构又分为二叉链（要用两个指针）和三叉链（要用到三个指针），数据结构专栏我用的都是二叉链，在后面C++专栏中的高阶数据结构我写三叉链

三、实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他特性

3.1 堆的概念与结构

堆具有以下性质

堆中某个结点的值总是不大于或不小于其父结点的值
堆总是一棵完全二叉树
堆顶是最值（最大值，最小值）

二叉树性质

对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

若i>0，i位置结点的双亲序号：(i-1)/2，要取整；i=0，i为根结点编号，无双亲结点
若2i+1<n（表示没有越界），左孩子序号：2i+1，2i+1>=n否则无左孩子
若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子

3.2 堆的实现

Heap（堆）底层是一个数组，在数组中存储每个结点的值，看上去逻辑结构是一个堆（二叉树），实际上底层是一个数组。该堆插入数据时，需要申请空间时，向操作系统申请空间

3.2.1 初始化及销毁

3.2.2 入堆（向上调整算法）+ 打印

由于堆是完全二叉树，结点是从左到右依次排列，用数组来实现堆的底层结构，数据存储的时候空间一定是连续的，插入数据时只有一种方式

堆分为两种，一种是大堆，一种是小堆，这里以大堆为例实现堆的插入

这里数组中有6个数据，这里入堆要先增容，初始情况：

这里插入数据80，先让80入在堆的后面，放到下标为6的位置，逻辑结构中也是56的右孩子，由于给的值比父节点大，此时还需要调整。

80向上调整，先要与父结点比较，已知孩子求父亲：(i-1)/2（结果取整），孩子结点的值比父结点大就进行数据的交换

再比较，将80和70进行调整

此时child再向上走，parent=(child-1)/2，0-1变为负数，不能再向上调整了，此时就是一个大堆了

还有一种情况，要插入的数据是60

交换之后child走到parent的位置

此时60的父结点比其本身的值要大，就不需要交换了

代码演示

实际分配的内存字节数是 newCapacity * sizeof(HPDataType)（元素个数 × 单个元素的字节大小）。

可以看到最后结果也是完美复合的

3.2.3 出堆（向下调整算法） + 判断堆是否为空

在堆中删除数据不同于数组直接删除数据，在堆中不论是删除数据还是取堆顶操作，操作的都是堆顶

如果出堆方式直接将堆顶的70删掉，在数组中将70删掉就要后面的数据整体往前移，再让size减减，这样整个堆的结构就乱套了，而且要调整的话代价很大

这里提供一种方法，将堆顶和数组的最后一个数据进行交换，然后size减减，数组中的最后一个数据70就出数据了，就不会破坏中间数据的父子关系了

此时要调整的代价就小很多了，让堆顶向下调整就好了

要将10向下调整，就要10与其左右孩子比较，谁大谁向上放。先将大孩子定义为10的左孩子，child=parent×2+1，child+1就是右孩子，30和56比较之后，child走到56的位置

孩子之间比较完了，就是孩子与父亲比较，此时56与10交换

继续向下调整，parent走到child的位置，再让child走到parent×2+1的位置

此时child越界了，其对应下标为5，说明56没有孩子，就没有接着向下调整的必要了

还有一种调整情况，这里将10向下调整

这里交换完成后parent走到child的位置，child=parent×2+1

此时child就要与child+1比较（左孩子与右孩子比较），但是此时child+1的位置没有数据，所以说在这里取child+1的数据可能会发生越界，所以接下来的代码中还要加一个条件，child+1<n

3.2.4 取堆顶

//取堆顶
HPDataType HPTop(HP* php);

下面写一个逻辑，循环的判断堆是否为空，如果不为空就把堆顶的数据取出来打印一下然后再出堆操作

结果得到了一个降序的序列，原因是堆顶在堆里面是一个最值

如果想要得到一个升序的序列就要建小堆，向上调整算法中的比较就要换一下，条件改为孩子比父亲小则进行交换

同理，出堆的时候，堆顶是最值，最小值放到最后的位置，最小值被删掉在向下调整算法中，原来是找最大的孩子向上放就是建大堆，建小堆就要把小的孩子向上放

这就是一个升序的序列了

3.3 堆的应用

上面可以看到循环取堆顶出堆可以得到一个有序的序列，也就是堆这样一个特殊的结构可以实现堆排序

3.3.1 堆排序

堆排序思路如上图，有了堆结构之后就可以循环的取堆顶，把堆顶保存在数组当中，最终得到一个有序的数组

根据以上思路就得到了下面的代码

看似没有问题，但这不是实际的堆排序

在冒泡排序中没有使用任意的数据结构就实现了数组数据的排序，在堆排序中要使用堆数据结构来实现数组的排序，还需要堆相关的操作

正确的堆排序是借助堆的思想来进行排序

3.3.1.1 向下调整算法建堆

堆排序首先要进行建堆，上面使用堆这个结构来实现错误的堆排序的代码中，把数组里的数据向堆中push了，实际上是向堆底层的数组去插入数据，实际上还是让数组变为堆结构

而在正真的堆排序代码中，形参就会传一个数组过来，可以直接将传过来的arr变为一个堆结构

这是一个数组转成的堆结构，但是其不是一个有效的堆结构

这里依旧使用向下调整算法建堆来建一个小堆，但是不能按照原方法从下标为0的位置开始调整了，因为其甚至不是一个有效的堆结构

这里的方法是先从最小的一棵子树开始调整，先调整小的，再一步一步调整大的，方向就是从右往左，从下往上，找最后一个结点的根就是25（parent），然后找左右孩子之中的最小值，因为只有一个孩子所以不需要比较左右孩子了

然后直接拿child和parent比较，10小10往上放，然后该子树就是一个小堆了

25调整完后parent直接减减一个就到了56，然后调整以56为根的这颗子树，根据parent找孩子，孩子求到的是左孩子，然后左右孩子中15最小

再拿孩子和父亲比较

调整完了之后parent走到child位置，child来到parent×2+1的位置，此时child越界，无法调整了

此时56这颗子树调整完了，是一个小堆接下来就要调整整棵二叉树了，原56继续减减，就回到了根结点（30），开始调整以30为根的堆

根据父亲求孩子，找孩子中的最小值，右孩子更小，child++

10小再与父亲比较，进行交换

调整完后，parent走到孩子的位置，child等于parent×2+1，来到了左孩子（25）

没有右孩子，直接孩子与父亲比较，交换

parent走到child，child×2+1此时越界，此时根结点调整完了，整个堆也调整完了，此时也是一个小堆了

乱序数组的建堆是从25开始，即第一个要调整的是最后一个结点的父结点，这里的n是6个数据，最后一个数据的下标是n-1，找最后一个结点的父结点是根据孩子找父亲，也就(n-1-1)/2，依次的调整顺序是25，56，30，30对应的下标为0，所以循环条件是i>=0。下标之间相隔为1，所以每次i减减

此时堆有了，就要while循环手动实现取堆顶出堆操作，让数组变为有序的

由于堆顶是最值，让其与最后一个数据交换

在这个数组当中，原本size是6，现在size减减变为了5

这里将不包含在内的10进行特殊标记了堆顶和10进行交换之后不是一个有效的堆结构了，现在对30到70进行建堆

已知parent找child，小的往上放，大的往下放，然后parent来到child位置，child=parent×2+1

此时30就是最小的，就不需要调整了，继续重复刚刚的步骤，拿堆顶和堆里最后一个数据（70）进行交换，然后size再减减，此时堆中就无15这个数据了，然后再进行调整

已知parent求孩子，找孩子之中的最小值（25），孩子和父亲比较，谁小谁放上

继续向下调整，parent来到child位置，child来到parent×2+1的位置

此时70没有孩子，child越界，此时也是一个小堆，继续重复刚刚的步骤

拿堆顶和最后一个数据进行交换，25此时不包含在堆中了，继续向下调整，已知parent求孩子，两个孩子30最小，孩子和父亲交换

继续向下调整，parent来到child位置，child来到parent×2+1，此时child越界，调整完了，依旧重复

根据父亲求孩子，只有一个孩子，谁小谁往上放

继续调整，此时child越界了，调整完了继续将最后一个数据和堆顶进行交换

此时就是一个有序的数组

总结：当前数组通过不断取堆顶和最后一个数据交换，向下调整建堆。就可以使得数组变成有序

排升序—建大堆排降序—建小堆

最后一次（end=1）交换是下标为0的数据（56）和下标为1的数据（70）进行交换，交换完成后endj减减，就来到下标为0的位置（70）。数组有序。所以循环的和最后一个位置数据交换的截至条件是end>0。

这里想要升序，把建堆操作改为建大堆就可以了

3.3.1.2 向上调整算法建堆

该结构现在还不是一个堆，只是一个二叉树

这里向上调整的时候，从数组的第一个数据一个一个来，可以当成是一个往堆中插入数据的思想，此时遍历数组的第一个数据（30），表示堆中只有一个数据，一个数据就是堆顶，不用调整

i++来到56，将30和56建成一个大堆结构

i继续加加，到25，拿25建堆后不用向上去调整

i++到15，这里15和30比较一下，也不用向上调整

i到70，70要向上调整，根据child求parent，要(child-1)/2

调整完成之后继续向上,child来到parent的位置，parent来到(child-1)/2的位置

谁大谁向上放

继续向上调整，child来到parent的位置，child已经为0了，就跳出循环

接下来i++来到10，10是25的左孩子

此时child比parent要小，不用调整了，此时就是一个大堆了，就可以拿堆顶和最后一个位置数据交换，然后再调整，使得数组是一个有序的

依旧符合下面规矩

排升序—建大堆排降序—建小堆

3.3.1.3 二者算法时间复杂度分析

两种算法都可以建堆，评估二者的好坏就要靠时间复杂度了

向上调整就是知道孩子，然后把孩子结点向上调整

该孩子结点向上调整几层，while就要循环几次，对于目前这个结点最差的情况就是向上调整到根结点，也就是要调整的层数就是while循环的次数

已知二叉树结点的个数为n，如何求解二叉树的层次？

前面满二叉树已知结点层次为k，总的结点个数n=2k-1

所以向上调整算法的时间复杂度就是(logn)

向下调整算法是根据父亲求孩子，把顶部的结点向下去调整，最差的情况就是顶部的结点调整到了叶子结点

所以向下调整算法的时间复杂度也为（logn）

可以看到二者的时间复杂度都为（logn）

刚刚只看了循环内部的两个算法复杂度（红框），现在结合循环一起来看

现在看向上调整算法建堆和向下调整算法建堆的时间复杂度，因为复杂度计算的是最差的情况，所以下面以满二叉树为例推理在满二叉树使用向上调整算法来建堆就要看堆中有多少结点，以及结点向上调整的层次，所以计算满二叉树向上调整建堆的时间复杂度，就要满足下面的公式

需要移动结点总的移动步数（循环的次数）：每层结点个数×每个结点向上调整次数（第一层调整次数为0），最后累加起来

左边是根据结点的层次求结点的总数，右边是根据结点的总数求结点的层次因为时间复杂度和结点的个数有关，所以h用n来替换

这里底数打不出来省略了

这里和上面向上调整算法建堆的时间复杂度相等

接下来看向下调整算法建堆结合循环的复杂度，依旧以满二叉树为例，时间复杂度与其结点个数有关，每层结点的个数以及每个结点向下调整的次数，将这些累加起来得到的就是循环的次数下面的图是反着分析的，左边是层数，右边是该层结点数，向下调整第h层都是叶子结点

叶子结点不能再向下调整了，所以第h层向下调整的次数为0，所以最后一层就不分析了

第h-1层最差的情况是向下移动一层，来到叶子结点的位置

对于根节点，最差的情况下是调整到叶子结点，一共是h层，所以要调整h-1层，以此类推

继续根据刚刚的公式：需要移动结点总的移动步数为：每层结点个数×向下调整次数，累加起来就是循环的次数

最后结果依旧h用n来替换由于大 O 符号描述的是算法运行时间的增长趋势，关注的是 “当输入规模 n 足够大时，哪个项主导了运行时间的增长”。

对于函数 (T(n) = n - log(n+1)：n 是线性项（增长速度为 “线性”，即随 n 成比例增长）；log(n+1) 是对数项（增长速度远慢于线性，属于 “低阶项”）

所以结合了循环的向下调整算法建堆的时间复杂度为O（n）

通过二者比较可以看到向下调整算法建堆的时间复杂度更低

那么为什么都是循环嵌套一个logn时间复杂度的算法，而向下调整算法和向上调整算法经过数学推理，最终得到的结果不一样呢？依旧从图中分析，先看向上调整算法建堆，分析的是结点从下往上挪

在这个图中，越往下走，结点个数越多，而且向上调整次数越多，图中红色箭头总的循环次数也就是调整总的次数=单个结点调整次数×每层结点个数

再看向下调整算法建堆

对应上一个图的绿箭头

这就是为什么向下调整算法的时间复杂度更低

堆排序时间复杂度为n+nlogn，化简得堆排序的时间复杂度就为nlogn，这在排序算法当中是一个比较优秀的时间复杂度

3.3.2 Top-K问题

Top-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了（可能数据都不能一下子全部加载到内存中），最佳的方式就是用堆来解决

有兄弟就说了，如果数据量很大，就算用堆去求解最大/小的前几个数据，依旧要把数据存起来形成一个堆结构，也就是要把数据放到数组当中，然后让所有的数据进行建堆，这也涉及把数据加载到内存中，这不是有同样的问题吗？

接下来我给出解决方案，这也是在面试的环节中面试官非常喜欢考察的一个问题，首先做一个补充

假设有10亿个整数，现在把这些数据存起来，就要消耗4个G的内存

这里1024×1025×1024结果有9个0，也就是大约为10亿个字节，整数在32位操作系统下是4个字节

假设这里只有1KB的内存，要用于建堆找这10亿个数据的最大/最小值，下面的黑框就相当于10亿个数据，10亿个数据用n来表示

这里就只需要创建一个堆，堆中只保存10亿个数据中的k个数据，这个数据量就很小了。

要找最大的前K个数据，建小堆，小堆的特征是堆顶是最小值，剩下的k-1个数据都比堆顶的值大，10亿个数据还剩下n-k个数据，接下来开始遍历这些数据

遍历拿到第一个数据，和这个只有k个数据的堆顶来比较，如果拿到的数据比堆顶大，将拿到的i放到堆顶，继续调整为小堆，此时堆顶又变为了最小值，继续取下一个数据循环此操作，将剩下的n-k个数据遍历完，此时这个只有k个数据的堆，里面的k个数据就是这10亿个数据当中最大的前K个数据，同理，求10亿个数据中最小的前K个数据也是如此

代码实现

这个问题最重要的就是十亿个数据，这十亿个数据肯定是不能存到内存当中的，最好是存在磁盘当中，在这里创建一个文件，文件之中需要有很多的数据，下面的代码就是用来造数据的

接下来就要读取data.txt文件，去找最大或最小的前k个数据

这里可以手动构造10个最大的数据（大于一百万的数据），来验证一下

这读取到的数据就是一个小堆了

当前Top-k时间复杂度

四、完整源码

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义堆结构
typedef int HPDataType;
typedef struct Heap {
	HPDataType* arr;
	int size;    //堆中有效数据个数
	int capacity;//堆中最多能存储的元素个数
}HP;

//初始化
void HPInit(HP* php);
//销毁
void HPDestory(HP* php);
//打印堆
void HPPrint(HP* php);

//交换
void Swap(int* x, int* y);
//入堆
void HPPush(HP* php, HPDataType x);
//向上调整算法
void AdjustUp(HPDataType* arr, int child);
//判断堆是否为空
bool HPEmpty(HP* php);
//出堆
void HPPop(HP* php);
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);
//取堆顶
HPDataType HPTop(HP* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include"Heap.h"

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

//销毁
void HPDestory(HP* php)
{
	assert(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");
}

//交换
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	//根据子结点求父结点
	int parent = (child - 1) / 2;
	//child为0时，parent为负数，就不能再调整了
	while (child > 0)
	{
		//建大堆：>
		//建小堆：<
		if (arr[child] < arr[parent])
		{
			//这里数据的交换是对数组里的数据进行交换
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;//跳出while循环
		}
	}
}

//入堆
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//空间不够需要扩容
	if (php->size == php->capacity)
	{
		//扩容
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	//空间足够，直接入堆
	php->arr[php->size++] = x;
	//向上调整
	AdjustUp(php->arr, php->size - 1);
}

//判断堆是否为空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

//向下调整算法
//判断是否越界要知道结点个数，参数n是堆中的结点个数
void AdjustDown(HPDataType* arr, int parent, int n)
{
	//根据父结点求子结点
	int child = parent * 2 + 1;
	while (child < n)
	{
		//建大堆：<
		//建小堆：>
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			//child指向右孩子
			child++;
		}
		//孩子和父亲比较
		//建大堆：>
		//建小堆：<
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

//出堆
void HPPop(HP* php)
{
	assert(!HPEmpty(php));
	//size是有效数据个数，size-1就是最后一个数据的位置
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	//删掉堆顶数据
	--php->size;
	//堆顶数据需要向下调整
	AdjustDown(php->arr, 0, php->size);
}

//取堆顶
HPDataType HPTop(HP* php)
{
	assert(!HPEmpty(php));
	return php->arr[0];
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void test01()
{
	HP hp; //创建堆结构变量
	HPInit(&hp);
	HPPush(&hp, 25);
	HPPush(&hp, 15);
	HPPush(&hp, 10);
	HPPush(&hp, 56);
	HPPush(&hp, 70);
	HPPush(&hp, 30);
	HPPrint(&hp);
	//HPPop(&hp);
	//HPPrint(&hp);
	//HPPop(&hp);
	//HPPrint(&hp);
	//HPPop(&hp);
	//HPPrint(&hp);
	//HPPop(&hp);
	//HPPrint(&hp);
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		printf("%d ", top);
		HPPop(&hp);
	}

	HPDestory(&hp);
}

//堆排序
void HeapSort01(int* arr, int n)//n是数组中的数据个数
{
	HP hp;//----使用数据结构-堆
	HPInit(&hp);
	//调用push将数组中的数据放入堆中
	for (int i = 0; i < n; i++)
	{
		HPPush(&hp, arr[i]);
	}
	int i = 0;
	//取堆顶，将堆顶数据导入数组中
	while (!HPEmpty(&hp))
	{
		int top = HPTop(&hp);
		arr[i++] = top;
		HPPop(&hp);
	}
	HPDestory(&hp);
}

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Swap(&arr[j], &arr[j + 1]);
			}
		}
	}
}

//堆排序--使用堆结构的思想
void HeapSort(int* arr, int n)
{
	//向下调整算法---建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, n);
	}
	////从数组里的第一个数据开始建堆，i从0开始到n-1的位置
	//for (int i = 0; i < n; i++)
	//{
	//	AdjustUp(arr, i);
	//}
	//取最后一个位置的数据，end始终指向数组的下标

	//时间复杂度nlogn
	int end = n - 1;
	//循环的和最后一个位置数据交换
	while (end > 0)//n
	{
		Swap(&arr[0], &arr[end]);
		//调整的时候不包含最后一个数据
		AdjustDown(arr, 0, end);//logn
		end--;
	}
}

void CreateNDate()
{
	//造数据
	int n = 100000;
	srand(time(0));
	//将文件名抽象为一个变量，方便后续文件操作
	const char* file = "data.txt";
	//以写的形式打开文件，在文件中写东西
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	//循环十万次
	for (int i = 0; i < n; ++i)
	{
		//生成的随机数小于1000000
		int x = (rand() + i) % 1000000;
		//将生成的值保存在data.txt文件中
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);//关闭文件，释放资源
}

void TopK()
{
	int k = 0;
	printf("请输入K：");
	scanf("%d", &k);
	const char* file = "data.txt";
	//打开文件，读取前k个数据
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen fail!");
		exit(1);
	}
	//申请空间大小为k的整型数组
	int* minHeap = (int*)malloc(sizeof(int) * k);
	if (minHeap == NULL)
	{
		perror("malloc fail!");
		exit(2);
	}
	//读取文件中k个数据放到数组中
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &minHeap[i]);
	}
	//数组调整建堆--向下调整建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}
	int data = 0;
	//遍历剩下n-k个数，与堆顶比较，谁大谁入堆
	//把读取到的数据临时存到data中，若读取到EOF,是读取到文件的结尾
	while (fscanf(fout, "%d", &data) != EOF)
	{
		if (data > minHeap[0])
		{
			minHeap[0] = data;
			AdjustDown(minHeap, 0, k);
		}
	}
	//打印堆中的数据
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap[i]);
	}
	printf("\n");
	fclose(fout);
}

int main()
{
	//CreateNDate();
	TopK();
	return 0;
}

int main1()
{
	//test01();
	int arr[6] = { 30,56,25,15,70,10 };
	printf("排序之前：\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	//HeapSort01(arr, 6);
	//BubbleSort(arr, 6);
	HeapSort(arr, 6);
	printf("排序之后：\n");
	for (int i = 0; i < 6; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");

	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-27，如有侵权请联系 cloudcommunity@tencent.com 删除

存储