目录
堆排序
整体思路
代码实现
Q1建大堆/小堆
Q2数据个数和下标
TopK问题
整体思路
代码实现
Q1造数据CreateData
Q2建大堆/小堆
- 建堆的两种方法
- 这里会用到前面的向上/向下调整/交换函数。向上调整&向下调整算法-CSDN博客
堆排序
整体思路
- 建堆（直接把数组搞成堆）升序：建大堆 降序：建小堆
- 利用堆删除的思想来进行堆排序 （就是模拟堆删除的过程，但是实际并不删除堆）
- 1：交换头尾
- 2：向下调整（除去最后一个元素&&最后一个元素已经排好序了）
- 3：循环重复上述过程
- 建队有两种方法：插入（向上调整建堆）/向下调整建堆（下篇细讲）
- 建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
代码实现
//堆排序:本质直接在数组里面排序
void test1(int* a, int size)
{
//方法1的时间/空间复杂度都很低
//方法2
//1.向上调整建堆 建堆--建的小堆--降序 建大堆--升序
for (int i = 0; i < size; i++)
{
AdjustUp(a, i);
}
//1.向下调整建堆
for (int i = (size - 1 - 1) / 2; i >= 0; i--)//i=0的时候到达根节点此时就是全部向下调整
{
Adjustdown(a, size, i);//这里的size不确定，但是肯定比size小所以取最大就size
}
//2.
while (size)
{
//交换
Swap(&a[0], &a[size - 1]);
//向下调整(除去已经排序好的元素）
Adjustdown(a, size-1, 0);
//到达下一个交换的位置
size--;
}
}
int main()
{
int a[10] = { 2,3,7,5,4,3,9,7,6,10 };
int size = sizeof(a) / sizeof(a[0]);//10个数==最后一个数的下一个数的下标
test1(a, size);
//3.打印
for (int i = 0; i < size; i++)
{
printf("%d ", a[i]);
}
return 0;
}Q1建大堆/小堆
升序：建大堆
降序：建小堆
Q2数据个数和下标
size：指向最后一个元素的下一个位置
交换首位元素：最后一个元素的下标size-1
出去排好的元素向下调整个数：为size-1（-1除去排好的元素）
TopK问题
TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
整体思路
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
- 用数据集合中前K个元素来建堆
- 前k个最大的元素，则建小堆；前k个最小的元素，则建大堆
- 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
- 将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
代码实现
void CreateDate()//创造数据
{
int n = 1000000;
srand((unsigned int)time(NULL));//随机数的种子
//打开文件
const char* file = "data.txt";//文件指针
FILE* fin = fopen(file, "w");//以写的形式打开文件状态指针
if (fin == NULL)//打开失败
{
perror("fopen error");
return;
}
//写文件
for (int i = 0; i < n; i++)
{
int r = (rand() + i) % 1000000;
fprintf(fin, "%d\n", r);
}
//关闭文件
fclose(fin);
}
void test2(int K)
{
//打开文件
const char* file = "data.txt";//文件指针
FILE* fout = fopen(file, "r");//以写的形式打开文件状态指针
if (fout == NULL)//打开失败
{
perror("fopen error");
return;
}
//读取文件
//开辟数组空间存放小堆
int* a = (int*)malloc(sizeof(int) * K);
if (a == NULL)
{
perror("malloc error");
return;
}
for (int i = 0; i < K; i++)
{
fscanf(fout, "%d", &a[i]);//读取放入数组
AdjustUp(a, i);//建小堆
}
//一直读取并且比较
int n = 0;
while (fscanf(fout,"%d", &n) != EOF)
{
if (a[0] < n)
{
a[0] = n;
Adjustdown(a, K, 0);
}
}
//打印
int i = 0;
for (i = 0; i < K; i++)
{
printf("%d ", a[i]);
}
//释放空间/关闭文件
free(a);
fclose(fout);
}
int main()
{
//CreateDate();//创造数据
int K = 8;
test2(K);//TopK问题--小堆--取前K个最大的数
return 0;
}Q1造数据CreateData
- 打开文件
- 写文件
- 关闭文件
- 随机数&随机数的种子&产生随机数
- 随机数最多3万个
- 文件指针&文件状态指针
- 想要产生的随机数在100万以内：%100万
- 测试：去文件里面修改值大于>100万的数，查看是否打印出来的是修改后的数据。
void CreateDate()//创造数据
{
int n = 1000000;
srand((unsigned int)time(NULL));//随机数的种子
//打开文件
const char* file = "data.txt";//文件指针
FILE* fin = fopen(file, "w");//以写的形式打开文件状态指针
if (fin == NULL)//打开失败
{
perror("fopen error");
return;
}
//写文件
for (int i = 0; i < n; i++)
{
int r = (rand() + i) % 1000000;
fprintf(fin, "%d\n", r);
}
//关闭文件
fclose(fin);
}
Q2建大堆/小堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
🙂感谢大家的阅读，若有错误和不足，欢迎指正
