数据结构 | 堆的向上调整和向下调整算法【奇妙的堆排序】
2023-04-18 16:09:20 时间
堆
一、堆的概念及结构
如果有一个关键码的集合K = { k0， k1， k2，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中。并满足：Ki <= K2*i+1 且 Ki <= K2*i+2 ( Ki >= K2*i+1 且 Ki >= K2*i+2 ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
堆的性质
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树
基本了解堆的概念后，我们来看看琢磨一下什么是大根堆和小根堆
- 从上图可以看出，对于【堆】而言，其实就是一种完全二叉树，但是呢，它又在完全二叉树的基础上再进一步形成一个区分，也就是分为【大根堆】和【小根堆】
- 可对于这种树形的结构，其实并不是它在内存中真正的样子，这只是我们为了更好地理解而想象出来的；它在内存中真正的样子应该是右边那样，也就是像一种数组的存储方式，对于这种逻辑结构和物理结构的区分，我在一文带你彻底搞懂单链表也有做过详细区分。那既然是数组，一定可以使用【下标】来访问其中的元素。
- 这其实就可以得出一种结论，就是这个堆中的各个结点直接它是存在一种关系的，我们在树和二叉树的基本概念讲到了父亲结点和孩子结点。那此时我们是否可以用下标来表示一下父亲结点和孩子结点直接的关系呢，就像下面这样👇
【lchild = parent * 2 + 1】 左孩子
【rchild = parent * 2 + 2】 右孩子
parent = （lchild - 1）/ 2 或者 parent = （rchild - 2）/ 2 ===> 【parent = (child - 1) / 2】
- 如果觉得难以理解，可以将下面的下标带入进入演算一下，就可以发现确实是这样
- 为了再进一步加深对堆的一个理解，我们来实际地看一下有关堆这一块的题目
- 可以看出，对于【堆】而言，要么是大堆，要么是小堆，不一定是呈现升序或者是降序，这涉及到的是我们后面的堆排序，但是对于父亲和孩子的关系来说，一定是父亲【<=或者>=】它的孩子，而且对于任何一个子树而言都必须成立，这才能对称做一个【堆】
二、向上调整算法⭐⭐
对于【堆】的概念初步建立后，接下去我们就要正式去学习一种算法，叫做【向上调整算法】
1、算法思路分析【孙子的谋权篡位之旅👑】
- 对于向上调整，从字面意思上看就是从下往上左一个调整，那具体是怎么一个调整法呢，我们看下面这张图
- 可以看到，我们在当前堆的最后一个空缺的位置插入一个新的结点，对于这个新的结点呢，它要影响的并不是整棵左子树，也不是右子树，而是它的父亲结点和祖先结点，因为对于【堆】来说，就是需要去比较它的父亲结点和孩子结点之间的关系
- 我们看到第一个小根堆，此时在末尾插入一个100，这个数很大，但是可以看到这是个小根堆，也就是小的在堆顶，大的在堆底，那么此时去比较这个【56】和【100】就可以看到是不需要做一个改变的，那既然它的爸爸都比它大了，那它爷爷👴就更不用说了，因为我们无需再往上进行一个比较
- 然后我们再来看到第二个堆，也就是大根堆，对于它我们可以知道大的在堆顶，小的在堆底；相信聪明的你很快就可以反应过来这是需要去进行一个向上不断地交换调整，也就是将这个【100】不断与它的父亲做一个比较，若是比它的父亲大，则做一个交换后再与它的爷爷做一个比较，若是比它爷爷还大，那么它就可以登顶王位👑了。具体的演示就像上图这样
- 这么看下来，对于【向上调整算法】其实就很像是一个逆子不断地往上爬，想要夺得家里那个最高地位的权利一般
2、代码详情解说
光是了解其思路可不够，我们还要能够写出代码，也就是将画出的一张张算法图转化为代码
- 首先，我们应该知道应该出入什么参数，这个【Hp】是堆这种数据结构的结构体，后面我们会讲到，然后就是需要有一个孩子结点，这就是新插入的这个孩子结点，我们需要对其进行一个是否需要调整的判断
void Adjust_UP(Hp* hp, int child)
- 有了这个新入的孩子后，我们就要去查找到它的父亲，因为是要和它的父亲去做一个对比，前面我们有说到过怎么通过一个孩子去找它的父亲，忘了的再翻上去找找哦
int parent = (child - 1) / 2;
- 找到之后呢就可以去进行一个比较了，若是孩子比它父亲来的大，那么就将它们俩进行一个交换即可，交换函数很简单，下面会给出
if (hp->a[child] > hp->a[parent])
swap(&hp->a[child], &hp->a[parent]); //交换孩子和父亲，逐渐变为大根堆
- 但是呢我们交换一次就可以了吗❓那当然不是，这是一个不断进行调整的过程，所以我们每次在交换完后需要再次去更新父亲和孩子的值，然后将这段逻辑放到一个循环里。若是调整到符合堆的性质了，就break跳出这个循环
- 对于这个循环的条件呢可以看到我是写了两种，一种是【parent >= 0】，一种则是【child > 0】，第一种不推荐，你可以去演算一下，假设当这个100交换到堆顶之后，【child】和【parent】就会再次做一个更新，那么此时他们就是都变成0了，若是将循环条件改为【parent >= 0】，那么就会再次进入这个循环，此时0 == 0，就会再次进入这个交换的逻辑，然后又去更新它们的值，此时就是一个无谓的更新，当【parent】被更新成为【-1/2】时此时再循环去进行一个判断的时候就会变成一个非正常的结束。所
- 以我们当孩子为0的时候，也就是当【100】交换到堆顶后进行一个更新之后就已经可以不需要再去判断
//while (parent >= 0) 这样写不好，程序会非正常结束
while (child > 0)
{
if (hp->a[child] > hp->a[parent])
{
swap(&hp->a[child], &hp->a[parent]); //交换孩子和父亲，逐渐变为大根堆
//迭代 —— 交替更新孩子和父亲
child = parent;
parent = (child - 1) / 2;
}
else {
break; //若是比较无需交换，则退出循环
}
}
以下是整体代码
/*交换函数*/
void swap(HpDataType* x1, HpDataType* x2)
{
HpDataType t = *x1;
*x1 = *x2;
*x2 = t;
}
/*向上调整算法*/
void Adjust_UP(Hp* hp, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0) 这样写不好，程序会非正常结束
while (child > 0)
{
if (hp->a[child] > hp->a[parent])
{
swap(&hp->a[child], &hp->a[parent]); //交换孩子和父亲，逐渐变为大根堆
//迭代 —— 交替更新孩子和父亲
child = parent;
parent = (child - 1) / 2;
}
else {
break; //若是比较无需交换，则退出循环
}
}
}
三、向下调整算法⭐⭐⭐⭐⭐
对于向下调整算法这一块，在后面堆的数据结构中的删除堆顶数据和堆排序都需要用到它，因此重点掌握
1、算法图解分析【高处不胜寒🆒趁早做打算】
- 对于向下调整算法，最主要的一个前提就是根节点的左右子树都要是大堆或者都要是小堆，就根结点不满足，才可以去进行一个向下调整
- 此时就需要使用到这个【向下调整算法】，当然我这个是大堆的调整，小堆的话刚好相反。原理：找出当前结点的两个孩子结点中教大的那一个换上来，将这个【18】换下去，但是呢此时还不构成大堆，因此我们还需要再去进行一个调整，一样是上面的找法，然后直到这个【18】的孩子结点到达【n - 1】就不作交换了，因为【n - 1】就相当于是位于数组下标的最后一个值
2、代码考究精析
清楚了向下调整算法的主要原理和思路，接下去我们就要将其转化为代码
- 首先对于向下调整算法来说我们需要传入的不是孩子，而是父亲，因为调整的是堆顶数据，也就是根节点，而对于根节点来说是没有父亲的，所以就是父亲，然后的话需要的是这个堆的大小【n】，因为这个我们在循环体的结束条件时需要用到
void Adjust_Down(int* a, int n, int parent)
- 上面是知道孩子求父亲，这里的话就是知道父亲求孩子了，但是有同学说，孩子不是有两个吗，为什么我只写了一个【child】，这里的话你也可以写成【lchild】和【rchild】，但是呢这在下面进行比较的时候代码会显得比较冗余，你可以先写写试试看，再和我这个做对比
- 因为我们是需要和孩子结点中大的那个做交换，因为我这里是直接假设左孩子比较大
int child = parent * 2 + 1;
- 接下去呢将左右孩子的值进行一个比较，若是右孩子来的大就将child++，也就顺其自然变成了右孩子。可以看到这个if判断里还加了一个【child + 1 < n】，这个的话其实就是进行一个右孩子的越界访问判断，因为我们是在进行一个不断向下调整的过程，因此肯定会到达倒数第二层，此时它的左孩子可能是存在的，但若是它的右孩子不存在了，那么在后面去访问这个【child + 1】就会变成越界访问，是一个非法操作
//判断是否存在右孩子，防止越界访问
if (child + 1 < n && a[child + 1] > a[child])
{
++child; //若右孩子来的大，则转化为右孩子
}
- 然后是循环内部的逻辑，和【向上调整算法】一样，就是一个比较和迭代更新的过程
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
下面是整段代码
/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent)
{
int child = parent * 2 + 1; //默认左孩子来得大
while (child < n)
{ //判断是否存在右孩子，防止越界访问
if (child + 1 < n && a[child + 1] > a[child])
{
++child; //若右孩子来的大，则转化为右孩子
}
if (a[child] > a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
四、堆的数据结构各接口算法实现
接下去我们来说说有关【堆】这个数据结构的各接口算法实现。没错，【堆】也可以是一种数据结构
结构体的定义及声明
- 首先看到结构体的定义及声明，是不是回想起了我们之前所学的顺序表，因为顺序表的底层其实也是一种数组
typedef int HpDataType;
typedef struct Heap {
HpDataType* a;
int size;
int capacity;
}Hp;
1、堆的初始化
- 首先的话就是堆的初始化，这一块代码很简单
- 当然你也可以在初始化这一块就把堆的数据存放空间给开出来，这个的话我是放在Push的时候直接去进行realloc
/*初始化堆*/
void HeapInit(Hp* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
2、堆的销毁
- 有了初始化，那一定得销毁，就是变回初始化时的样子。而且要将开出来存放数据的空间释放
/*销毁堆*/
void HeapDestroy(Hp* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
3、堆的插入【⭐】
- 构建了一个基本的堆，接下去就要往这个空间中放入数据。可以看到，对于数组，我都会去写一段扩容逻辑，之前在初始化的时候没有开出来的空间一并在这里开出，如果看不懂的话可以去看看我的顺序表这一章节，有详细说明
- 可以看到，除了有这个扩容逻辑之外，在底部还有一个【向上调整算法】，我们在插入新的元素后始终要保持原先的堆是一个【大堆】或者【小堆】，所以要去进行一个向上调整，这里的【hp->size - 1】值得就是当前新入的结点，我在顺序表章节有讲到过，size始终是位于末梢元素的下一个位置，因此-1的话就可以访问到末梢元素了，也就是形参中的孩子结点
/*堆的插入*/
void HeapPush(Hp* hp, HpDataType x)
{
assert(hp);
//扩容逻辑
if (hp->size == hp->capacity)
{
int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HpDataType* tmp = (HpDataType*)realloc(hp->a, newCapacity * sizeof(HpDataType));
if (tmp == NULL)
{
perror("fail realloc");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
Adjust_UP(hp, hp->size - 1);
}
4、堆的删除【⭐】
- 有插入，那一定要有删除，这一块我会重点分析✍
- 首先可以来看下代码，可以看到很显目的一句，就是交换【a[0]】和【a[hp->size - 1]】，这其实值的就是堆顶的结点和堆顶的末梢结点，为什么先要交换它们呢，我们来分析一下
/*堆的删除*/
void HeapPop(Hp* hp)
{
assert(hp);
assert(hp->size > 0);
//首先交换堆顶和树的最后一个结点 —— 易于删除数据，保护堆的结构不被破坏
swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--; //去除最后一个数据
Adjust_Down(hp->a, hp->size, 0);
}
改写族谱，关系紊乱😵
- 若是我们什么都不做，直接去删除一下这个堆顶的数据，后面的结点就需要前移，此时的原本的孩子结点就会变成父亲，父亲呢可能又会变成孩子。这其实也就乱了，是吧，原本呢【49】和【34】说我们要做一辈子的好兄弟，但是呢当它们的爸爸没了之后，【49】就想要当上爸爸。原本的【27】是【34】的远方亲戚，但是呢现在却成了兄弟，所以心疼【34】3秒钟🦌🦌🦌
- 所以说直接去删除这个堆顶的数据一定不行，会对整个堆造成一定的影响，那我们该怎么办呢❓
- 此时就像代码中写的一样，我们可以先去交换一下堆顶和堆底末梢的数据，然后将交换下来的数删除，这样既可以删除这个堆顶的数据，也不会影响整棵树的结构，整体算法图如下
- 通过这组算法图我们可以看出，堆顶数据不符合，但是其左右子树均符合大堆或者是小堆的时候，此时我们就可以去进行一个【向下调整算法】，这个过程就是我上面分析过的，一直调整到其孩子结点为n的时候就表明其孩子不存在了，就无需再向下进行调整
- 可以看到，在Pop完数据进行向下调整后，依旧是保持一个大堆
5、取堆顶的数据
- 这块很简单，因为堆顶的数据就是数组的首元素，因此直接return【hp->a[0]】即可
/*取堆顶数据*/
HpDataType HeapTop(Hp* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->a[0];
}
- 上面说到过，结构体中的【size】是指向当前堆底末梢数据的后一个位置，也就相当于【n】，因此求数据个数直接return【hp->size】即可
6、堆的数据个数
/*返回堆的大小*/
size_t HeapSize(Hp* hp)
{
assert(hp);
return hp->size;
}
7、堆的判空
- 堆的判空就是当数据个数为0的时候
/*判断堆是否为空*/
bool HeapEmpty(Hp* hp)
{
assert(hp);
return hp->size == 0;
}
8、堆的构建
对于堆的创建这一块，有两种方法，一种是直接利用我们上面所写的【Init】和【Push】联合向上调整建堆；另一种则是利用数据拷贝进行向下调整建堆
Way1
- 首先我们来看第一种。很简单，就是利用【Init】和【Push】联合向上调整进行建堆
/*建堆*/
void HeapCreate1(Hp* hp, HpDataType* a, int n)
{
assert(hp);
HeapInit(hp);
for (int i = 0; i < n; ++i)
{
HeapPush(hp, a[i]);
}
}
Way2√
- 接着是第二种，比较复杂一些，不会像【向上调整算法】一样插入一个调整一个，而是为这个堆的存放数据的地方单独开辟出一块空间，然后将数组中的内容拷贝过来，这里使用到了memcpy，不懂的小伙伴可以先去了解一下它的用法
- 当把这些数据都拿过来之后，我们去整体性地做一个调整，那就不可以做向上调整了，需要去进行一个【向下调整】，我们通过图解来看看
HeapInit(hp);
HpDataType* tmp = (HpDataType*)malloc(sizeof(HpDataType) * n); //首先申请n个空间用来存放原来的堆
if (tmp == NULL)
{
perror("fail malloc");
exit(-1);
}
hp->a = tmp;
//void * memcpy ( void * destination, const void * source, size_t num );
memcpy(hp->a, a, sizeof(HpDataType) * n); //将数组a中n个数据拷贝到堆中的数组
hp->size = n;
hp->capacity = n;
- 可以看到，对于即将要调整的根结点，首先我们要回忆一下向下调整算法的先决条件，就是当要调整的结点的左右子树均为大堆或者小堆，只有待调整的结点不满足时，才可以使用这个算法，但是可以看到，【4】下面的两个子树均不是大堆（我这里默认建大堆），那有同学说这该怎么办呢？此时我们应该先去调整其左右子树，使他们先符合条件才行
- 然后可以看到左子树这一边，当【47】作为要调整的结点时，它的左右子树依旧不是一个大堆，此时我们需要做的就是再去调整其左右子树，直到其符合条件为止，那此时我们应该去调整【3】【14】，那还需要再去调整其左右子树吗？可以看到【1】和【36】确实也是不符合，但是呢对于叶子结点来说是没有孩子的，所以调不调整都一个样，因此我们只需要从倒数第二层开始调整就行，也就是最后一个非叶子结点，即【14】
- 那要如何去找到和这个【14】呢，这个好办，我们可以知道它的孩子，就是堆底的末梢元素，那对于数组来说最后一个数据的下标为【n - 1】，在上面有说到过已知孩子结点去求结点其父亲结点【(child - 1)/2】，那这里的【child】我们使用【n - 1】带入即可，然后通过循环来一直进行调整，但是在调整完【14】这棵子树后要怎么越位到【3】这棵子树呢，上面说到了，堆存放在一个数组中，因此我们直接将这个【parent - 1】就可以继续往前调整了。最后直到根节点为止就是我们上面讲解【向下调整算法】时的样子
//向下调整
/*
* （n - 1）代表取到数组最后一个数据，不可以访问n
* (x - 1)/2 代表通过孩子找父亲
*/
for (int i = ((n - 1) - 1) / 2; i >= 0; --i)
{
Adjust_Down(hp->a, n, i);
}
- 下面是【向下调整算法建堆】执行的全过程
测试💻
说了这么多，还不知道写得代码到底对不对，我们来测试一下
- 首先的话是基本的接口功能测试
- 然后把向上建堆和向下建堆一起看，好作辨析。
- 可以看到，均可以完成建堆的操作
五、两种调整算法的复杂度精准剖析⏳
- 开头讲了两种堆的调整算法，分别是【向上调整】和【向下调整】，在接口算法实现Push和Pop的时候又用到了它们，以及在建堆这一块我也对它们分别做了一个分析，所以我们本文的核心就是围绕这两个调整算法来的，但是它们两个到底谁更加优一些呢❓
- 这里就不做过多解释，直接看图即可
1、向下调整算法【重点掌握】
2、向上调整算法
- 好，我们来总结一下，对于【向上调整算法】，它的时间复杂度为O(NlogN)；对于【向下调整算法】，它的时间复杂度为O(N)
- 很明显，【向下调整算法】来得更优一些，因为向下调整随着堆的层数增加结点数也会变多，可是结点越多调整得就越少，因为在一些大型数据处理场合我们会使用向下调整
- 当然在下面要讲的堆排序中我们建堆也是利用的向下调整算法，所以大家重点掌握一个就行
六、堆的实际应用
1、堆排序【⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐⭐】
讲了那么久的堆，学习了两种调整算法以及它们的时间复杂度分析，接下去我们来说说一种基于堆的排序算法——【堆排序】
升序建大堆 or 小堆❓
- 在上面解说的时候，我建立的默认都是大堆，但是在这里我们要考虑排序问题了，现在面临的是【升序】，对于升序就是数组前面的元素小，后面的元素大，这个堆也是基于数组建立的，那就是要堆顶小，堆顶大,很明显就是建【小堆】
- 一波分析猛如虎🐅，我们通过画图来分析是否可以建【小堆】
- 可以看到，对于建小堆来说，原本的左孩子结点就会变成新的根结点，而右孩子结点就会变成新的左孩子结点，整个堆会乱，而且效率并不是很高，因此我们应该反一下，去建大堆
//建立大根堆（倒数第一个非叶子结点）
for (int i = ((n - 1) - 1) / 2 ; i >= 0; --i)
{
Adjust_Down(a, n, i);
}
如何进一步实现排序❓
- 有了一个大堆之后，如何去进一步实现升序呢，这里就要使用到我上面在Pop堆顶数据的思路了，也就是现将堆顶数据与堆底末梢数据做一个交换，然后对这个堆顶数据进行一个向下调整，将大的数往上调。具体过程如下
- 对照代码，好好分析一下堆排的全过程吧
/*堆排序*/
void HeapSort(int* a, int n)
{
//建立大根堆（倒数第一个非叶子结点）
for (int i = ((n - 1) - 1) / 2 ; i >= 0; --i)
{
Adjust_Down(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[0], &a[end]); //首先交换堆顶结点和堆底末梢结点
Adjust_Down(a, end, 0); //一一向前调整
end--;
}
}
- 看一下时间复杂度，建堆这一块是O(N)，调整这一块的话就是每次够把当前堆中最的数放到堆底来，然后每一个次大的数都需要向下调整O(log2N)，数组中有N个数需要调整做排序，因而就是O(Nlog2N)。
- 当然你可以这么去看：第一次放最大的数，第二次是次大的数，这其实和我们上面讲过的向上调整差不多了，【结点越少，调整越少；结点越多，调整越多】，因此它也可以使用之前我们分析过的使用的【错位相减法】去进行求解，算出来也是一个O(Nlog2N)。
- 最后将两段代码整合一下，就是O(N + Nlog2N)，取影响结果大的那一个就是O(Nlog2N)，这也就是堆排序最终的时间复杂度
2、Top-K问题
对堆这一块还有一个经典的问题就是Top - K：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。
复杂度分析
- 现在假设我要在N个数中找前K个最大的数字，那你会采用什么样的方法去求解呢？要结合我们所学习的【堆】
代码详情
- 经过分析之后呢我们就选择了第二种方式建堆去进行求解前K个最大的数。下面是代码
- 在这里我使用到了从文件中读出数据的方法，要结合C语言中的【文件操作】，若是忘记的小伙伴可以去回顾一下。以下代码的具体思路就是：通过一个文件指针首先去访问到这个文件，首先读出k个数放入数组中，有了这个k个数以后，我们就要先去建立一个堆，这里记住要建【小堆】，接着继续去读取剩下的数字，将每次读取的数组与堆顶的数进行一个比较，若是比堆顶的数要来的大，那么就进行一个替换，然后对这个新进来的数进行一个向下调整，保持这个堆依旧还是一个【小堆】。一直这么循环往复，直到文件中的数读取完毕，然后输出数组中的所有数就是我们维护的堆中的前K个最大的数
/*TopK*/
void HeapTopK()
{
//1.使用一个文件指针指向这个文件
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//2.读出前k个数放入数组中
int k = 5;
int max[5];
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &max[i]);
}
//3.建立k个堆
for (int i = ((k - 1) - 1) / 2; i >= 0; --i)
{
Adjust_Down(max, k, i);
}
//4.继续读取剩下的数据
/*
* 不断和堆顶数据做比较，比堆顶大就入堆，然后继续向下调整
*/
int val = 0;
while ((fscanf(fout, "%d", &val)) != EOF) //不停读取剩下的数据
{
if (val > max[0])
{
max[0] = val; //替换为堆顶
Adjust_Down(max, k, 0); //将其做向下调整
}
}
//5.打印数组中的数据，观看TopK个最大的数
for (int i = 0; i < k; ++i)
{
printf("%d ", max[i]);
}
printf("
");
fclose(fout);
}
- 我们来看一下运行结果
- 除了从固定的文件中读取数据进行运算，我们还可以自己写入一些数据进行查找
- 可以看到，我这里使用的是一个随机值的写入，这一块也是我们在C语言中讲到过的，要使用到rand()和srand()，过程很简单，当然这里的【n】和【k】是由我自己来输入，因此下面的数组我们要设置成动态开辟。代码如下
int n, k;
puts("请输入n和k的值：");
scanf("%d%d", &n, &k);
srand((unsigned int)time(NULL)); //随机种子
FILE* fin = fopen("data2.txt", "w"); //若有，则打开写入；若无，则创建写入
int randVal = 0;
for (int i = 0; i < n; ++i)
{
randVal = rand() % 1000000; //随机生成数字
fprintf(fin, "%d
", randVal); //将每次随机生成的数字写入文件中
}
fclose(fin);
///
// 获取文件中前TopK个值
//1.使用一个文件指针指向这个文件
FILE* fout = fopen("data2.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//2.读出前k个数放入数组中
int* max = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &max[i]); //此处无需加
，因为读取时空格和回车自动作为分隔
}
//3.建立k个堆
for (int i = ((k - 1) - 1) / 2; i >= 0; --i)
{
Adjust_Down(max, k, i);
}
//4.继续读取剩下的数据
/*
* 不断和堆顶数据做比较，比堆顶大就入堆，然后继续向下调整
*/
int val = 0;
while ((fscanf(fout, "%d", &val)) != EOF) //不停读取剩下的数据
{
if (val > max[0])
{
max[0] = val; //替换为堆顶
Adjust_Down(max, k, 0); //将其做向下调整
}
}
//5.打印数组中的数据，观看TopK个最大的数
for (int i = 0; i < k; ++i)
{
printf("%d ", max[i]);
}
printf("
");
fclose(fout);
- 来看看运行结果
七、整体代码展示【需要自取】
Heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <time.h>
typedef int HpDataType;
typedef struct Heap {
HpDataType* a;
int size;
int capacity;
}Hp;
/*初始化堆*/
void HeapInit(Hp* hp);
/*建堆*/
void HeapCreate1(Hp* hp, HpDataType* a, int n); //向上调整
void HeapCreate2(Hp* hp, HpDataType* a, int n); //向下调整
/*堆的插入*/
void HeapPush(Hp* hp, HpDataType x);
/*堆的删除*/
void HeapPop(Hp* hp);
/*取堆顶数据*/
HpDataType HeapTop(Hp* hp);
/*判断堆是否为空*/
bool HeapEmpty(Hp* hp);
/*返回堆的大小*/
size_t HeapSize(Hp* hp);
/*输出堆*/
void HeapDisplay(Hp* hp);
/*销毁堆*/
void HeapDestroy(Hp* hp);
/*交换函数*/
void swap(HpDataType* x1, HpDataType* x2);
/*向上调整算法*/
void Adjust_UP(Hp* hp, int child);
/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent);
/*堆排序*/
void HeapSort(int* a, int n);
/*TopK*/
void HeapTopK();
void HeapTopK2();
Heap.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
/*初始化堆*/
void HeapInit(Hp* hp)
{
assert(hp);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
/*建堆*/
void HeapCreate1(Hp* hp, HpDataType* a, int n)
{
assert(hp);
HeapInit(hp);
for (int i = 0; i < n; ++i)
{
HeapPush(hp, a[i]);
}
}
/*建堆*/
void HeapCreate2(Hp* hp, HpDataType* a, int n)
{
assert(hp);
HeapInit(hp);
HpDataType* tmp = (HpDataType*)malloc(sizeof(HpDataType) * n); //首先申请n个空间用来存放原来的堆
if (tmp == NULL)
{
perror("fail malloc");
exit(-1);
}
hp->a = tmp;
//void * memcpy ( void * destination, const void * source, size_t num );
memcpy(hp->a, a, sizeof(HpDataType) * n); //将数组a中n个数据拷贝到堆中的数组
hp->size = n;
hp->capacity = n;
//向下调整
/*
* （n - 1）代表取到数组最后一个数据，不可以访问n
* (x - 1)/2 代表通过孩子找父亲
*/
for (int i = ((n - 1) - 1) / 2; i >= 0; --i)
{
Adjust_Down(hp->a, n, i);
}
}
/*交换函数*/
void swap(HpDataType* x1, HpDataType* x2)
{
HpDataType t = *x1;
*x1 = *x2;
*x2 = t;
}
/*向上调整算法*/
/*
* 孙子很可能当上爷爷
*/
void Adjust_UP(Hp* hp, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0) 这样写不好，程序会非正常结束
while (child > 0)
{
if (hp->a[child] > hp->a[parent])
{
swap(&hp->a[child], &hp->a[parent]); //交换孩子和父亲，逐渐变为大根堆
//迭代 —— 交替更新孩子和父亲
child = parent;
parent = (child - 1) / 2;
}
else {
break; //若是比较无需交换，则退出循环
}
}
}
/*堆的插入*/
void HeapPush(Hp* hp, HpDataType x)
{
assert(hp);
//扩容逻辑
if (hp->size == hp->capacity)
{
int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
HpDataType* tmp = (HpDataType*)realloc(hp->a, newCapacity * sizeof(HpDataType));
if (tmp == NULL)
{
perror("fail realloc");
exit(-1);
}
hp->a = tmp;
hp->capacity = newCapacity;
}
hp->a[hp->size] = x;
hp->size++;
Adjust_UP(hp, hp->size - 1);
}
/*向下调整算法*/
/*
* 高处不胜寒 —— 即使是堆顶，也是不会稳定的，做不住的，会被人打下来，因此需要向下调整
*/
void Adjust_Down(int* a, int n, int parent)
{
int child = parent * 2 + 1; //默认左孩子来得大
while (child < n)
{ //判断是否存在右孩子，防止越界访问
if (child + 1 < n && a[child + 1] < a[child])
{
++child; //若右孩子来的大，则转化为右孩子
}
if (a[child] < a[parent])
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
/*堆的删除*/
void HeapPop(Hp* hp)
{
assert(hp);
assert(hp->size > 0);
//首先交换堆顶和树的最后一个结点 —— 易于删除数据，保护堆的结构不被破坏
swap(&hp->a[0], &hp->a[hp->size - 1]);
hp->size--; //去除最后一个数据
Adjust_Down(hp->a, hp->size, 0);
}
/*取堆顶数据*/
HpDataType HeapTop(Hp* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->a[0];
}
/*判断堆是否为空*/
bool HeapEmpty(Hp* hp)
{
assert(hp);
return hp->size == 0;
}
/*返回堆的大小*/
size_t HeapSize(Hp* hp)
{
assert(hp);
return hp->size;
}
/*输出堆*/
void HeapDisplay(Hp* hp)
{
for (int i = 0; i < hp->size; ++i)
{
printf("%d ", hp->a[i]);
}
printf("
");
}
/*销毁堆*/
void HeapDestroy(Hp* hp)
{
assert(hp);
free(hp->a);
hp->a = NULL;
hp->size = hp->capacity = 0;
}
/*堆排序*/
void HeapSort(int* a, int n)
{
//建立大根堆（倒数第一个非叶子结点）
for (int i = ((n - 1) - 1) / 2 ; i >= 0; --i)
{
Adjust_Down(a, n, i);
}
int end = n - 1;
while (end > 0)
{
swap(&a[0], &a[end]); //首先交换堆顶结点和堆底末梢结点
Adjust_Down(a, end, 0); //一一向前调整
end--;
}
}
/*TopK*/
void HeapTopK()
{
//1.使用一个文件指针指向这个文件
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//2.读出前k个数放入数组中
int k = 5;
int max[5];
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &max[i]);
}
//3.建立k个堆
for (int i = ((k - 1) - 1) / 2; i >= 0; --i)
{
Adjust_Down(max, k, i);
}
//4.继续读取剩下的数据
/*
* 不断和堆顶数据做比较，比堆顶大就入堆，然后继续向下调整
*/
int val = 0;
while ((fscanf(fout, "%d", &val)) != EOF) //不停读取剩下的数据
{
if (val > max[0])
{
max[0] = val; //替换为堆顶
Adjust_Down(max, k, 0); //将其做向下调整
}
}
//5.打印数组中的数据，观看TopK个最大的数
for (int i = 0; i < k; ++i)
{
printf("%d ", max[i]);
}
printf("
");
fclose(fout);
}
void HeapTopK2()
{
int n, k;
puts("请输入n和k的值：");
scanf("%d%d", &n, &k);
srand((unsigned int)time(NULL)); //随机种子
FILE* fin = fopen("data2.txt", "w"); //若有，则打开写入；若无，则创建写入
int randVal = 0;
for (int i = 0; i < n; ++i)
{
randVal = rand() % 1000000; //随机生成数字
fprintf(fin, "%d
", randVal); //将每次随机生成的数字写入文件中
}
fclose(fin);
///
// 获取文件中前TopK个值
//1.使用一个文件指针指向这个文件
FILE* fout = fopen("data2.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
//2.读出前k个数放入数组中
int* max = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &max[i]); //此处无需加
，因为读取时空格和回车自动作为分隔
}
//3.建立k个堆
for (int i = ((k - 1) - 1) / 2; i >= 0; --i)
{
Adjust_Down(max, k, i);
}
//4.继续读取剩下的数据
/*
* 不断和堆顶数据做比较，比堆顶大就入堆，然后继续向下调整
*/
int val = 0;
while ((fscanf(fout, "%d", &val)) != EOF) //不停读取剩下的数据
{
if (val > max[0])
{
max[0] = val; //替换为堆顶
Adjust_Down(max, k, 0); //将其做向下调整
}
}
//5.打印数组中的数据，观看TopK个最大的数
for (int i = 0; i < k; ++i)
{
printf("%d ", max[i]);
}
printf("
");
fclose(fout);
}
test.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void test()
{
Heap h;
int a[] = { 4,47,9,3,14,8,27,1,36,22 };
int sz = sizeof(a) / sizeof(int);
HeapInit(&h);
for (int i = 0; i < sz; ++i)
{
HeapPush(&h, a[i]);
}
HeapDisplay(&h);
printf("当前堆的大小为：%d
", HeapSize(&h));
HeapPop(&h);
HeapDisplay(&h);
printf("当前堆顶数据为：%d
", HeapTop(&h));
printf("当前堆的大小为：%d
", HeapSize(&h));
}
void test2()
{
Heap h;
int a[] = { 4,47,9,3,14,8,27,1,36,22 };
int sz = sizeof(a) / sizeof(int);
HeapCreate1(&h, a, sz);
HeapDisplay(&h);
HeapDestroy(&h);
}
void test3()
{
Heap h;
int a[] = { 4,47,9,3,14,8,27,1,36,22 };
int sz = sizeof(a) / sizeof(int);
HeapCreate2(&h, a, sz);
HeapDisplay(&h);
HeapDestroy(&h);
}
void test4()
{
int a[] = { 4,47,9,3,14,8,27,1,36,22 };
int sz = sizeof(a) / sizeof(int);
HeapSort(a, sz);
for (int i = 0; i < sz; ++i)
{
printf("%d ", a[i]);
}
printf("
");
}
void test5()
{
Heap h;
int a[] = { 4,47,9,3,14,8,27,1,36,22 };
int sz = sizeof(a) / sizeof(int);
HeapCreate2(&h, a, sz);
HeapDisplay(&h);
int k = 3;
printf("当前堆的前三高频数据为
");
while (k--)
{
printf("%d ", HeapTop(&h));
HeapPop(&h); //删除对应数据后会进行向下调整算法，因此每次进来堆顶都是最大的数据
}
HeapDestroy(&h);
}
void test6()
{
//HeapTopK();
HeapTopK2();
}
int main(void)
{
//test();
//test2();
//test3();
//test4();
//test5();
test6();
return 0;
}
/*
* 向上调整要求：插入进去数据后依旧要保持这是一个堆
* 向下调整要求：需要左子树和右子树都是堆
*/
八、总结与提炼
在本文中我们主要围绕【向上调整算法】和【向下调整算法】来展开对【堆】这一数据结构的学习
- 在开头，我们首先初步了解了这两个算法的核心思想，接着就开始学习【堆】这个数据结构以及它的一些接口算法实现，里面的【Push】和【Pop】中也使用到了上面的调整算法
- 其中我们还对堆的构建有了两种方法，也是围绕这两种算法的展开，并且各自分析了它们的【时间复杂度】。对于向上调整来说，复杂度为O(Nlog2N)，结点越少，调整越少；结点越多，调整越多。而对于向下调整来说，复杂度为O(N)，结点越少，调整越多；结点越多，调整越少。在数据量很大的情况下更优一些
- 最后我们还讲到了两种有关【堆】的时间应用：一个是堆排序，它是八大排序算法之一，是一个比较高效的排序算法，我通过画图展现了堆排的全过程，然后分析得出它的时间复杂度为O(Nlog2N)；接着我们又了解到了一个堆的实际应用，就是【Top-K】问题，可以用来解决生活中需要在一堆数据中取出前K个最大或最小数的场合，这还是【堆】中比较经典的一类问题呢，要好好看哦
- 看到这里，你对【堆】这种数据结构有没有一个全面的认识了呢😄
以上就是本文所有讲解的全部内容，若有问题请于评论区留言或者私信我，觉的好的话就留下你的三连吧❤️
相关文章
- 谈谈你最熟悉的System.DateTime[上篇]
- IoC+AOP的简单实现
- 谈如何边做事，边提高
- C#会重蹈覆辙吗？系列之4：华而不实的C#析构器
- 综述：编程语言的发展趋势及未来方向
- 一致性Hash算法(KetamaHash)的c#实现
- 十年技术，不要再迷茫
- 想成为优秀的技术人员你必须做到的几件事情
- C# 4动态编程新特性与DLR剖析
- 如何让普通变量也支持事务回滚？
- WPF Multi-Touch 开发：Windows 7 安装多点触屏模拟器
- 基于Visual Studio 2010 进行敏捷/Scrum模式开发
- NHibernate3剖析：Query篇之NHibernate.Linq自定义扩展
- 程序员应知——团队精神
- NHibernate3剖析：Query篇之NHibernate.Linq标准查询
- Microsoft Ribbon for WPF 正式发布
- 编程累了，一起来看电视吧，实战Windows 7的Windows Media Center。
- 程序员的语言“艳遇史”（七）——电台播音员scheme
- 我眼中的Visual Studio 2010架构工具
- 关于腾讯的胡思乱想：你的软件凭什么挣钱