赞
踩
目录
由于堆的本质是满二叉树,且堆实现的底层结构也和二叉树有关,所以在这里我们需要先介绍一下树的相关知识
如上是一棵树
之所以叫做树,是因为他看起来像是一棵倒挂的树,根朝上,叶子朝下,如上,我们的 1 号节点就是这棵树的根,而 2、3、4 号都是 1 的子树
但是有一个点需要注意:子树之间是不能相连的,或者说是不能成环的,如下:
这样就不是一棵树了,因为子树之间相连了
如上,这也不是一棵树
我们对照着下图来帮助理解
一看有那么多,可能有人会觉得很难记,但其实只需要记住其中几个比较重要的就好了,其他的只需了解即可
要记的:节点的度、叶节点、父节点、子节点、树的高度或深度、森林、祖先
我们该怎么表示一棵树呢?
我们每一个节点都有不同的子节点,说不定这个节点有 1 个子节点,下一个节点就有 3 个子节点,如果用链表的话,我们应该在链表节点里面定义几个指针呢?
所有链表的方法是想不通的,那有人可能会说:我们用顺序表吧,只需要让每一个树的节点里面都放上一个顺序表就可以了,结构如下:
- typedef int TDataType;
- typedef struct TreeNode
- {
- TDataType val;
- //顺序表
- struct TreeNode** a;
- int size;
- int capacity;
- }TN;
但是不知各位有没有觉得,这太麻烦了,每个节点里面都放一个顺序表,效率也低
那有没有更好的办法呢?
有的,这种方法叫左孩子右兄弟表示法
我们可以定义两个指针,一个指向自己的孩子,一个指向自己的兄弟
我们还是拿这棵树来举例
我们可以看到,我们只需要用左孩子指针指向最左边的节点,无论父节点的度为多少,都可以用右兄弟指针来表示
如果我们要遍历树的话,那我们只需要像遍历链表一样将数据遍历一遍,就能够表示整棵树了
表示的代码如下:
- typedef int TDataType;
- typedef struct TreeNode
- {
- TDataType val;
- struct TreeNode* leftchild;
- struct TreeNode* rightbrother;
- }TN;
每个节点的度不大于 2 的树,就是二叉树
简单点理解就是:一个父节点只能有 2 个以下的孩子,可以有一个两个甚至没有,但是不能超过两个
如上三棵树都是二叉树
如上,这棵树就不是二叉树
而二叉树是有左子树右子树之分的,如下:
这两种树是非常特殊的,先来说一说满二叉树,如下:
如上,这就是一棵满二叉树,那评判是否是满二叉树的标准是什么呢?
如果这棵树每一层的节点都满了,那么我们就说这棵树是满二叉树
如上三棵树都是满二叉树
如上,这棵树就不是一棵满二叉树
完全二叉树就是最后一层(第 n 层)的节点是从左到右依次排序的,且单看 1 ~ n-1 层是满二叉树
如上,这棵树就不是完全二叉树
但是这棵树就是完全二叉树(二叉树分左子树和右子树)
这棵树是满二叉树,同时也是完全二叉树
由此看来,满二叉树是一种特殊的完全二叉树,完全二叉树不一定是满二叉树,但是满二叉树一定是完全二叉树
就像是正方形与长方形之间的关系一样
我们先来看一棵完全二叉树
顺序存储的本质就是拿数组来存树内节点的数据,如下:
假设父节点叫 parent,左孩子叫 leftchild,右孩子叫 rightchild,根据一定的数学知识可以得出:
但如果是单算 parent 的话,其实上述两种方法得出的结果是一样的,因为编程中的除是不取余数的,所以两者之间的区别就是一个余 1 一个没有余数,但是得出的结果是相同的
leftchild 和 rightchild 按上述算式反推即可
- typedef int TDataType;
- typedef struct TreeNode
- {
- struct TreeNode* a;
- int size;
- int capacity;
- }TN;
但是用数组来存储树的节点只适合完全二叉树
如上这棵二叉树,如果我们直接将这里面的每个节点放进数组里的话,那么你会发现
我们在上面总结的结论用不了了,如果要满足的话,我们就需要将其中个别节点忽视,比如置空
但是如果这样的话,那么我们就会发现,我们就会发现我们有大量的空间浪费
综上,顺序存储更适合完全二叉树,如果不是完全二叉树的话,那么就需要用接下来要讲到的链式存储
因为是二叉树,每个节点的度最大也不超过 2,所以我们在定义树的节点的时候,只需要每个节点里面都放两个指针,一个指向左孩子,一个指向右孩子,假如没有右孩子,我们就另其指向空(NULL)
如果要遍历的话,就需要递归展开,这个内容和今天要讲的堆排序并无太大关系,这里就暂时不做讨论
代码如下:
- typedef int TDataType;
- typedef struct TreeNode
- {
- TDataType val;
- struct TreeNode* leftchild;
- struct TreeNode* rightchild;
- }TN;
堆的本质是二叉树,而且还是完全二叉树
而堆里面分为了大堆和小堆
由于我们是用顺序表存储的堆,实现堆的底层逻辑就是顺序表,所以我们在存储是选的是顺序存储
如下:
- typedef int HPDatatype;
-
- typedef struct Heap
- {
- HPDatatype* a;
- int size;
- int capacity;
- }HP;
其本质就是顺序表
所以我们在进行初始化操作时,我们就相当于是对顺序表进行初始化
即将指向动态空间的指针置为空,再将 size(有效数据个数)和 capacity(顺序表总容量)置为 0 即可
代码如下:
- void HPInit(HP* php)
- {
- assert(php);
- php->a = NULL;
- php->capacity = 0;
- php->size = 0;
- }
由于开辟的是动态空间,而且由于是顺序表而非链表,所以我们开辟的空间在物理上是连续的
所以,我们只需 free 掉空间,随后将指针置为空防止野指针问题,最后将 size 和 capacity
置为 0 即可
代码如下:
- void HPDestroy(HP* php)
- {
- assert(php);
- free(php->a);
- php->a = NULL;
- php->capacity = 0;
- php->size = 0;
- }
由于我们在堆中只有这一个插入(链表中有头插、尾插),所以我们不需要另外用一个函数来包装
先要判断一下堆是否满了或是根本没有开辟空间,如果满了或没开空间的话,我们才需要开辟
这里我们可以借用三目操作符:(注:下文中的 php 是传过来的顺序表)
int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
可以看到,我们定义了一个新变量 newcapacity,如果顺序表为空,那么我们就返回 4(这里以 4 为例,为空返回什么都无所谓),如果是满了,那我们就 realloc 扩展空间
接着就是老生常谈的步骤了:realloc 扩展、判断是否返回 NULL、顺序表中变量的改变
代码如下:
- //开辟空间
- HPDatatype* tmp = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*newcapacity);
- //判断是否返回 NULL
- if (tmp==NULL)
- {
- perror("realloc fail!");
- return;
- }
- php->a = tmp;
- php->capacity = newcapacity;
接着,我们就该在顺序表的第 size 个位置处插入数据,size(随后有效个数)++
php->a[php->size++] = x;
假如我们现在要建一个小堆,那我们插入数据之后,你能保证插入数据之后他还是小堆吗?
显然不能,如下:
小堆的要求是父节点 <= 子节点
上图我们假如插入的是一个 5,插入之前是小堆,但插入了 5 之后显然就不是了
这时我们就可以使用向上调整法来改变一下了
所谓向上调整法,就是从要调整的数据起,找到其父节点,随后进行比较
如果父节点 > 子节点(假设要建成小堆),那么我们就将两个数据交换一下(可以单独封装一个函数Swap,后续要复用)
接着,让原子节点走到父节点的位置,原父节点再向上寻找父节点(parent = (child-1) / 2)
不断遍历,直到子节点为 0,循环结束
可能有人会疑惑,如果该数据在向上移动的时候,其兄弟节点比他还小呢?
其实这种情况并不存在,因为我们是插入一个数据向上调整一次,所以在下一个数据来之前,这就已经是一个处理好的小堆了
代码入下:
- //交换函数封装
- void Swap(HPDatatype* p1, HPDatatype* p2)
- {
- HPDatatype tmp = *p1;
- *p1 = *p2;
- *p2 = tmp;
- }
- //向上调整
- void AdjustUp(HPDatatype* a,int child)
- {
- int parent = (child - 1) / 2;
- while (child > 0)
- {
- if (a[child] < a[parent])
- {
- Swap(&a[child], &a[parent]);
- child = parent;
- parent = (parent - 1) / 2;
- }
- else
- {
- break;
- }
- }
- }
不同于顺序表,堆的销毁不是销毁最下面的数据(堆最下层那么多个数据,也不知道删哪个,而堆顶就只有一个数据)
由于这是顺序表,所以堆顶就对应着第 0 个位置的数据。有人就会想啊,我们可不可以直接向前挪动数据覆盖第 0 个位置的数据?
答案是否定的,因为如果这么做了的话,那关系就乱了,原本的兄弟变成了爸爸,原本的叔叔变成了爸爸,原本的外甥变成了兄弟,关系全乱了,逻辑层面的关系被打乱,我们就无法再次遍历了,只能重新建立逻辑关系,但这一来二去,效率就低了
所以此方法想不通。这时就有一个相当厉害的算法可以解决这个问题:向下调整法
向下调整法如下:
首先将堆顶的数据与顺序表最尾部的数据进行交换,size-- 代表这个数不存在了,随后向下调整
如果 parent < child(这里假设建小堆),我们就交换数据
由于不知道 leftchild 和 rightchild 哪个更小,所以我们需要使用假设法找到小的那个孩子
接着让原 parent 走到 原 child 的位置,再根据 child = parent * 2 + 1 找到下一个需要调整的节点,直到 child > 顺序表总容量,循环结束
首先我们先来说一说什么是假设法,我们就以上面选小的那个孩子来举例:
假设法的基本原理就是,先假设左边那个是小的孩子,定义一个变量 tmp 并将左孩子的值赋给 tmp,然后再比较一下,如果左边那个不是小的孩子( if 语句内),再将右孩子的值赋给 tmp。如此一来,我们的变量 tmp 内部装着的就是小的那个孩子的值
上述代码如下:
- int child = parent * 2 + 1;
-
- //循环内部
- if (child + 1 < n && a[child + 1] < a[child])
- child++;
循环调整就是:让父母先等于孩子的值,找到下一次要调整的父节点。
接着让子节点根据数学知识( child = parent *2 + 1 )与假设法找到下一次要调整的子节点
上述代码如下:
- void AdjustDown(HPDatatype* 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 = child * 2 + 1;
- }
- else
- {
- break;
- }
- }
- }
-
- void HPPop(HP* php)
- {
- assert(php);
- assert(php->size > 0);
- Swap(&php->a[0], &php->a[php->size - 1]);
- php->size--;
-
- AdjustDown(php->a, php->size, 0);
- }
由于我们的堆是用顺序表来存储的,所以堆顶就对应着顺序表第 0 个位置的数据,我们只需要返回顺序表第 0 个位置的数据即可
上述代码如下:
- HPDatatype HPTop(HP* php)
- {
- assert(php);
- return php->a[0];
- }
由于堆的底层是顺序表,所以我们判断一个堆是否为空的标准和顺序表是一摸一样的,只需要判断其中的 size(有效数据个数)是否为 0 即可
同时我们也不需要用 if 语句进行判断,直接这么写:
- bool HPEmpty(HP* php)
- {
- assert(php);
- return php->size == 0;
- }
如果 size 等于 0,代表堆为空,就会返回 1
如果 size != 0,就意味着不为空,返回 0
我们知道,向上调整法最好的情况就是不调整,插入的数据刚好符合要求就不需要调整了
但是最坏的情况就是要调整高度次,从最下面一层一直调整到堆顶
注:^为次方,2^0 读作 2 的 0 次方
如上所示,我们假设总共有 N 个数,高度为 h 层
由上图我们可以知道:
N = 2^0 + 2^1 + 2^2 +……+ 2^(h-2) + 2^(h-1)
这是一个等比数列,而等比数列求和我们在高中时就学过了,但是可能公式已经不记得了,那我这里就给各位用错位相减法再推一遍
2N = 2^1 + 2^2 + 2^3 +……+ 2^(h-1) + 2^h
N = 2^0 + 2^1 + 2^2 +……+ 2^(h-2) + 2^(h-1)
—————————————————————上减下
N = 2^h - 2^0 =2^h - 1
所以 h = log(N+1) 注:以2为底时2可忽略不写
综上,由于向上调整法最坏的情况要调整高度次,又 h = log(N+1),所以向上调整法的时间复杂度就是 0(N) = logN
同样,向下调整法最坏的情况也是从堆的一头到另一头(堆顶到最底层)
也就是说,最坏的情况下,向下调整法需要调整高度次
根据我们在向上调整法时得出的结论可知:h = log(N+1)
所以向下调整法的时间复杂度与向上调整法相同,均为 0(N) = logN
- int main()
- {
- int arr[] = { 60, 35, 22, 56, 12, 77, 99 };
- HP php;
- HPInit(&php);
-
- //将数据一一放入顺序表中
- for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
- {
- HPPush(&php, arr[i]);
- }
- //排序
- while (!HPEmpty(&php))
- {
- printf("%d\n", HPTop(&php));
- HPPop(&php);
- }
-
- HPDestroy(&php);
- return 0;
- }
所谓建堆,就是先将数据先全部存进顺序表中。存完数据之后,再对数据进行调整
我们先来讲一讲调整数据之前的步骤:
首先我们有多少个数据是已知条件,假设为 n 个数
既然是建堆,我们就需要 malloc 一块空间,判断完是否返回空指针之后,我们就需要将数据拷贝到顺序表中,最后才是调整(大堆&小堆)
上述代码如下:
- assert(php);
- //malloc开辟空间
- HPDatatype* tmp = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
- //判断返回的是否是空指针
- if (!tmp)
- {
- perror("malloc fail");
- return;
- }
- php->a = tmp;
- //拷贝数据
- memcpy(php->a, a, sizeof(HPDatatype) * n);
- php->capacity = n; php->size = n;
这里可能有人对 memcpy 有点疑惑,这里我简单讲一讲:
简单来说,这个函数的作用是将数据从一个地方转移到另一个地方,然后返回一个指向目的地的指针(但是是 void* )
在这里我们不需要其返回值,我们要的只是其转移数据的功能
第一个参数是你要把数据传到哪里去(传地址)——目的地
第二个参数是你要将哪里的数据传过去(传地址)——起点
第三个参数是传过去的所有数据总共占多少字节
但是接下来就面临一个问题——我们是要用向上调整还是向下调整?
总共要调整的次数就是:
F(h) = 2^1*1 + 2^2*2 +……+ 2^(h-1)*(h-1)
根据错位相减法:
2F(h) = 2^2*1 + 2^3*2 +……+ 2^h*(h-1)
F(h) = 2^1*1 + 2^2*2 +……+ 2^(h-1)*(h-1)
——————————————————上减下
F(h) = 2^h * (h-1) + 2
又因为 h = log(N+1) 以二为底
F(N) = (N+1) * (log(N+1) - 1) + 2
显然,时间复杂度就是 O( N * logN )
我们向下调整不能直接从上面开始调整,如果你把第一层的节点调完了,第二层你要从哪里开始调呢?只能再建堆。但是再建的话效率就太低了
所以我们在使用向下调整的时候,我们就从倒数第二层的最右边的那个节点开始调整即可
因为最后一层不需要向下调整
而我们也可以通过数学公式找到倒数第二层的最右边的那个节点
假设总数为 n,该节点就是 (n-1)/2,上文 二叉树的存储->顺序存储 中有提到
总共要调整的次数就是:
F(h) = 2^0 * (h-1) + 2^1 * (h-2) + 2^2 * (h-3) +……+ 2^(h-2) * 1
根据错位相减法:
2F(h) = 2^1 * (h-1) + 2^2 * (h-2) + 2^3 * (h-3) +……+ 2^(h-1) * 1
F(h) = 2^0 * (h-1) + 2^1 * (h-2) + 2^2 * (h-3) +……+ 2^(h-2) * 1
———————————————————————————上减下
F(h) = 2^1 + 2^2 + 2^3 +……+ 2^(h-2) + 2^(h-1) - 2^0*(h-1)
- 2^0*(h-1) 可以写成 -h+1,而 1 也可以写成 2^0,所以上述表达式可以写成:
F(h) = 2^0 + 2^1 + 2^2 + 2^3 +……+ 2^(h-2) + 2^(h-1) - h
中间部分是等比数列求和,这里就不再演示了,直接给出结果:
F(h) = 2^h - 2^0 - h
又因为 h = log(N) 以2为底可忽略不写
F(N) = N - log(N+1)
显然,时间复杂度就是 O(N)
可能有人会不理解,得出来的明明是 N - log(N+1),为什么结果却是 0(N) ?
这么·说吧:
当N为1000时,logN约等于10
当N为100万时,logN约等于20
当N为10亿时,logN约等于30
这么看来,当N特别大时,logN就越能忽略不计,如是而已
每个数据都向上调整时,时间复杂度为 O(N*logN)
每个数据都向下调整时,时间复杂度为 O(N)
假设我有10亿个数据,logN约等于30
我给每个数据都向上调整时,需要调整 10亿*30 约 300亿次
而当我给每个数据都向下调整时,需要调整 10亿次
可能有人会好奇:为什么两种方法看起来差不多,可是效率却完全不一样呢?
这是因为我们在向上调整时,将最后一层的每个数据都进行了调整。而最后一层的数量占了总数量的大约二分之一
而向下调整时刚好避开了最后一层,达到的效果又相同,效率自然就提高了
两相比较之下,我们自然是选择向下调整法
- void HPInitArray(HP* php, HPDatatype* a, int n)
- {
- assert(php);
- HPDatatype* tmp = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
- if (!tmp)
- {
- perror("malloc fail");
- return;
- }
- php->a = tmp;
- memcpy(php->a, a, sizeof(HPDatatype) * n);
- php->capacity = n; php->size = n;
-
- for (int i = (php->size - 2) / 2; i >= 0; i--)
- {
- AdjustDown(php->a, php->size, i);
- }
- }
首先我们需要清楚的是,我们要做的是排序,是排序!!!
假如我们现在要将一个数组排成降序的,即从大到小排,如下:
我们现在要对这么一个数组进行排列(降序)
试想一下,如果我们在排降序的时候建大堆的话,那么应该是越上面的数据就越大
那这时假设,我的 10 已经到最上面了(上面的数据中10最大),接下来该怎么排呢?
我现在是在排序,我的10已经排好,那我就不需要动他了
剩下的数我们能再建堆吗?显然是不能的,原因有二:
1、 如果再以第二个数据为起始建堆,那么这时我们的关系就乱了,父子变兄弟,叔侄变父子,简直是倒反天罡
2、 如果再建堆的话,那么我现在将第二个数给排好了,那么我是不是应该以第三个数为起点继续建堆啊,那么我们来算一算时间复杂度:
建第一个堆是 N,第二个堆是 N-1,第三个是 N-2……最终其时间复杂度是 O(N^2),和冒泡排序是同样的效率,那如果这样的话,我为什么不直接选择冒泡排序而费老鼻子劲建堆呢?
那降序不能建大堆,那我们……建小堆?如果建小堆的话,那我们建完之后呈现的是从小到大,但是我们要的是从大到小啊
不急,建小堆是对的,至于建完了小堆之后如何降序排列,且听我细细道来
现在我们要的是降序排列(从大到小),那么此时我们建了小堆之后,已知最上面的数据是最小的
如果我们现在将首位的数据互换,是不是意味着我要的降序排列中的最后一位已经排好了
这时我再 有效数据个数--,这个数据就无效了但是依然存在
随后将最上面的数进行向下调整,最上面的数就变成了第二大的
在不断调整之下,我们就用小堆排好了降序
算一下时间复杂度:
综上,总的时间复杂度为 N + N*logN,也就是 O(N*logN)
- void heapsort(int* a,int n)
- {
- //建小堆,从大到小排序
- for (int i = (n - 2) / 2; i >= 0; i--)
- {
- AdjustDown(a, n, i);
- }
- int end = n - 1;
-
- while (end)
- {
- Swap(&a[0], &a[end]);
- AdjustDown(a, end--, 0);
- }
- }
-
- int main()
- {
- int a[] = { 6,8,5,7,9,3,2,4,1,0 };
- heapsort(a,sizeof(a)/sizeof(int));
- return 0;
- }
由于没有加打印,这里就直接看监视窗口吧,可以看到,我们是已经排序成功了的!
根据我们上文讲堆排序时建大堆与小堆问题的思想,我们只需要反过来建堆,随后将数据从后开始排序
如果我们要选出堆中的前 10 个最大的数据的话,那我们就可以建一个小堆,头尾交换后数据个数-1,最后将数据向下调整,如此往复,最后得到的就是一个降序排列的数组,我们取前十个即可
但是问题来了:
如果我现在有 100亿 个整形,找到其最大的 10 个数据,我难道要开辟一个超级大的空间来建堆、交换、调整吗?
100亿个整形是一个什么样的概念呢?1GB=1024MB,1MB=1024KB,1KB=1024byte
综上,1GB大约等于10亿个byte,一个整形 = 4byte,所以要储存这些数据的话,我们就需要大约40GB,代价未免太大了
所以,我们可以使用另外一种做法:我们现在要最大的前 10,那我就建一个只有 10 个节点的堆
来一个数据就和堆顶的数据比较,比堆顶大,就进到堆里,向下调整。比堆顶小,就不做处理,找下一个数据
这里就有一个问题:我是要建大堆还是小堆?
这里要建一个小堆,试想一下:如果你建了一个大堆,那当我最大的那个数把堆顶占了之后,也无需向下排序,因为他已经排好位置了,那后面的数据如果有前 10 大的,比最大的小,不做处理,下一个数,这是不是就出错了呀?
而我们建完了小堆之后,大的都跑到下面去了,并不会影响数据的正常遍历,所以我们建小堆
首先我们需要建一万个整形的话,可以使用文件函数,写随机值在里面
代码如下:
- void CreateNData()
- {
- //创建10000个数
- int n = 10000;
- //随机数种子
- srand((unsigned int)time(0));
- //创建文件
- const char* file = "data.txt";
- FILE* fin = fopen(file, "w");
- if (fin == NULL)
- {
- perror("fopen fail");
- return;
- }
- //在文件内写入数据
- for (int i = 0; i < n; i++)
- {
- int x = rand() % 1000000;
- fprintf(fin, "%d\n", x);
- }
- //关闭文件
- fclose(fin);
- }
这个地方看不懂没关系,只需要知道这是一种写数据到文本文件里的方式
我在这里简单解读一下:
首先我们定义了变量n,n的值就代表着我们要建多少个数据,随后就是创建文件data.txt,打开文件,获得指向该文件的文件指针 fin
最后就是一个 for 循环将随机数放进文件中,上面%1000000 是为了控制大小,方便我们后续判断结果是否正确
我们上述的创建文件只是将文件给创建出来,并在文件内放入了10000个数据
现在我们需要读取这个文件的内容,所以需要使用 fopen,随后判断是否返回的是空指针
- const char* file = "data.txt";
- FILE* fout = fopen(file, "r");
- if (fout == NULL)
- {
- perror("fopen fail");
- return;
- }
接着我们定义变量k,代表你要找的是前几个数的值
随后 malloc 一块空间作为堆,大小为 k 个 int。创建完之后将文件前 k 个数据都放进堆内
- printf("请输入要找top前几个数:");
- int k = 0;
- scanf("%d", &k);
-
- int* minheap = (int*)malloc(sizeof(int) * k);
- if (minheap == NULL)
- {
- perror("malloc fail");
- return;
- }
- //读数据进堆
- for (int i = 0; i < k; i++)
- {
- fscanf(fout, "%d", &minheap[i]);
- }
创建完堆之后,我们就需要将整个堆进行排序,这里用到向下调整法(效率比向上调整法要高)
而我们要排序的数从第 (k-1-1)/2 的位置开始。其中 k-1 是最后一个数据的位置,再 -1 除 2 就是公式了,上文 二叉树的存储方式中有详细讲解,这里就不再过多赘述了
- //建堆
- for (int i = (k - 2) / 2; i >= 0; i--)
- {
- AdjustDown(minheap, k, i);
- }
建完堆之后,我们就到一一比对数据的环节了
拿一个数,跟堆顶比对一下:如果比堆顶大,那就将堆顶直接覆盖掉,随后向下排序。如果比堆顶小,那么我们就不做处理,直接换到下一个数据进行比较
如此往复之下,最后前 k 个最大的数据就被留了下来,只是顺序并不是从大到小排好的而已
最后将数据进行打印,我们的 TopK 就找到了!!!
如果要对其进行从大到小排序的话,那可以用到我们上面说到的堆排序:建小堆、首尾互换,最小的数就排好了,随后向下调整,重复上述操作。最后的结果就是从大到小排好了
这里大家知道就好,就不做排序了
- void topk()
- {
- printf("请输入要找top前几个数:");
- int k = 0;
- scanf("%d", &k);
-
- const char* file = "data.txt";
- FILE* fout = fopen(file, "r");
- if (fout == NULL)
- {
- perror("fopen fail");
- return;
- }
-
- int* minheap = (int*)malloc(sizeof(int) * k);
- if (minheap == NULL)
- {
- perror("malloc fail");
- return;
- }
- //读数据进堆
- for (int i = 0; i < k; i++)
- {
- fscanf(fout, "%d", &minheap[i]);
- }
- //建堆
- for (int i = (k - 2) / 2; i >= 0; i--)
- {
- AdjustDown(minheap, k, i);
- }
- //一个个比对
- int x = 0;
- while (fscanf(fout, "%d", &x) != EOF)
- {
- if (x > minheap[0])
- {
- minheap[0] = x;
- AdjustDown(minheap, k, 0);
- }
- }
- //打印数据
- for (int i = 0; i < k; i++)
- {
- printf("%d ", minheap[i]);
- }
- fclose(fout);
- }
如果有需要今天代码的小伙伴可以点击下方的 gitee 链接
赞
踩
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。