文章目录
- 前言
- 一、堆排序
- 1.1 排序思想
- 1.2 堆排序过程(图解)
- 1.3 堆排序代码(升序为例)
- 二、TOP-K问题
- 2.1 TOP-K问题思路
- 2.2 随机生成随机数并存入文件
- 2.3 建小堆取前 k 个最大的数
前言
在学习堆排序和TOP-K问题之前,大家需要先熟悉两个算法(即
向上调整
和向下调整
算法),这两大算法可谓是它们的核心。话不多说,我们直接上手。
一、堆排序
注意:当要求排序为升序,在建堆时需要建成大堆,反过来当要求降序,在建堆时就需要建成小堆。
1.1 排序思想
堆排序是一种有效的排序算法,它的 核心思想 是
将一个无序数组构建成一个大顶堆(或小顶堆)
,然后将堆顶元素(最大值或最小值)与堆尾元素互换,之后将剩余的元素重新调整为大顶堆(或小顶堆),以此类推,直到整个数组有序。
- 当要求排序为升序时,我们希望输出的结果是
从小到大
。为了满足这个需求,在建堆时需要将较大的元素放在堆顶,这样在每次交换后,最大的元素会被放在数组的最后面。因此,在建堆过程中需要将数组建成大顶堆。 - 相反,当要求排序为降序时,我们希望输出的结果是
从大到小
。为了满足这个需求,在建堆时需要将较小的元素放在堆顶,这样在每次交换后,最小的元素会被放在数组的最后面。因此,在建堆过程中需要将数组建成小顶堆。
这里我们以升序为例,如图:
1.2 堆排序过程(图解)
1.3 堆排序代码(升序为例)
typedef int HPDataType
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 (parent >= 0)
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
//child = (child - 1) / 2;
//parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
// 向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 假设左孩子小,如果假设错了,更新一下
if (child + 1 < size && 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 HeapSort(int* a, int n)
{
//建大堆
//向上调整建对堆0(N*logN)
/*for (int i = 1; i < n; i++)
{
AdjustUp(a, i);
}*/
//向下调整建堆
// (找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整)0(N)
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
二、TOP-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
2.1 TOP-K问题思路
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
用数据集合中前K个元素来建堆
- 前k个最大的元素,则建小堆
- 前k个最小的元素,则建大堆
用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
- 将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
2.2 随机生成随机数并存入文件
//产生一千万个随机数
void CreateNDate()
{
// 造数据
int n = 10000000;
srand(time(0)); //srand()最多产生三万多个随机数
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (size_t i = 0; i < n; ++i)
{
int x = (rand() + i) % 10000000; //+i减少随机数的重复
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
【运行结果】:
生成 0~9999999 的随机数
2.3 建小堆取前 k 个最大的数
将 “data.txt” 文件中的数据依次读取建小堆,最后堆中的数据就是文件中最大的前 k
个数。
//向上调整 --- 小堆
void AdjustUp(HPDataType* a, int child)
{
int parent = (child - 1) / 2;
//while (parent >= 0)
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
//child = (child - 1) / 2;
//parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
// 向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 假设左孩子小,如果解设错了,更新一下
if (child + 1 < size && a[child + 1] < a[child])
{
++child;
}
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
// 取前k个最大的数
void PrintTopK(const char* file,int k)
{
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
//建一个k个数的小堆
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc error");
return;
}
//读取前k个,建小堆
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
AdjustUp(minheap, i);
}
//读取所有数据,建成小堆,最大的前k个数据就在堆中
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]);
}
printf("\n");
free(minheap);
fclose(fout);
}
运行结果:
【打开文件修改数据,测试程序正确性】:
修改数据后的运行结果:
🔥💖以上TOP-K问题只是取前k个最大数据的例子,取前k个最小数据与此类似,这里博主就不再赘述,希望这篇文章能够帮到大家,期待大家的三连支持🤞