自学内容网 自学内容网
自学内容网 > 正文

TOP-K问题

🕗 发布于 2024-10-08 17:18 算法  

目录

TOP-K问题

1.对TOP-K问题的理解

1.1.TOP-K问题定义

1.2.TOP-K问题的解决思路

1.3.以求N个数据中的前K个最大元素为例，阐述建堆来解决TOP-K的原理

1.4.TOP-K问题的类型

2.类型1：数据量N较小，可以全部加载到内存中。求数据量N的前K个最大的元素或者最小的元素。

2.1.求前K个最大的元素，建小堆。

(1)解决思路

(2)代码

2.2.前K个最小的元素，建大堆。

(1)解决思路

(2)代码

2.3.类型1的时间复杂度和空间复杂度的计算过程

(1)时间复杂度O(N * logK)

(2)空间复杂度O(1)

3.类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。求数据量N的前K个最大的元素或者最小的元素。

3.1.求前K个最大的元素，建小堆。

(1)解决思路

(2)代码

3.2.前K个最小的元素，建大堆。

(1)解决思路

(2)代码

3.3.类型2的时间复杂度和空间复杂度的计算过程

求解前K个最大元素的时间复杂度和空间复杂度：

(1)时间复杂度O(N * logK)

(2)空间复杂度O(K)

4.TOP-K问题的整个工程

4.1.TOP-K.h

4.2.TOP-K.c

4.3.test.c测试函数

TOP-K问题

1.对TOP-K问题的理解

1.1.TOP-K问题定义

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

1.2.TOP-K问题的解决思路

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

最佳的方式就是用堆来解决，基本思路如下：
1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素

1.3.以求N个数据中的前K个最大元素为例，阐述建堆来解决TOP-K的原理

当我们想要找到N个数据中前K个最大元素时，我们采用以下步骤：

  • 建立小堆：首先，我们从数据集中取出前K个元素，并构建一个小堆。在这个堆中，堆顶元素是这K个元素中最小的。

  • 遍历剩余元素：接着，我们遍历数据集中的剩余N-K个元素。对于每个元素：

    • 如果它比堆顶元素大，那么它有可能属于最大的K个元素之一。因此，我们用这个新元素替换掉堆顶元素，并进行向下调整操作（也称为堆化）以重新维护最小堆的性质。
    • 向下调整操作确保了新加入的较大元素能够“下沉”到堆的适当位置，而较小的元素则被“推”到堆顶或堆的上层。

  • 维护小堆：通过这个过程，我们确保了堆中始终保存着当前遇到的最大K个元素。当遍历完所有元素后，堆中的K个元素即为所求的最大K个元素。

1.4.TOP-K问题的类型

(1)类型1：数据量N没那么大，K很小，这N个数可以放在内存中。求数据量N的前K个最大的元素或者最小的元素。

(2)类型2：数据量N很大，K很小，这N个数内存存不下，只能存放在硬盘文件中。求数据量N的前K个最大的元素或者最小的元素。

2.类型1：数据量N较小，可以全部加载到内存中。求数据量N的前K个最大的元素或者最小的元素。

2.1.求前K个最大的元素，建小堆。

(1)解决思路
  • 在原数组中使用数组的前K个元素建立一个小堆。
  • 遍历数组剩余的N-K个元素，并与堆顶元素比较。
  • 如果当前元素大于堆顶元素，则替换堆顶元素，替换后并对此时的堆顶元素进行向下调整，通过向下调整保持数组前K个元素依然是个小堆。
  • 当数组剩余的N-K个元素都遍历完了，则最终小堆中的元素即为所求的前K个最大元素(注意：这前K个最大元素不一定是有序的)。
(2)代码
//交换两个元素的函数
void swap(int* p1, int* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}


//建小堆的向下调整
void AdjustDown2(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;

while (child < n)
{
//让child始终指向当前双亲的左右孩子中最小的那个孩子
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;
}

}


//TOP-K问题
//类型1：数据量N较小，可以全部加载到内存中。建小堆求数据量N的前K个最大的元素。

void PrintArrMaxTopK(int* a, int n, int k)
{
// 1.用数组a中前k个元素建小堆来解决求N个数中最大的前K个元素。(注意：由于利用向下调整函 
    数建堆的时间复杂度是O(N)，所以我们使用向下调整函数来建堆)

int parent = 0;
for (parent = (k - 1 - 1) / 2; parent >= 0; parent--)
AdjustDown2(a, k, parent);

// 2.将数组a中剩余n-k个元素依次与堆顶元素进行比较，若剩余n-k个元素有比小堆堆顶元素大的 
    则这两个元素就交换。交换完后对此时的堆顶元素(即数组首元素a[0])进行向下调整以此来要保持 
    数组a中前k个元素依然是个小堆。

int cmp = n - k;//cmp表示比较次数。
int i = k;//下标i是用来遍历数组a中剩余n-k个元素的。
while (cmp--)
{
//(1)堆顶元素a[0]与数组a剩余的n-k个元素进行比较。
        //若堆顶元素a[0]比数组a剩余元素a[i]要小，则要交换且交换后数组前k个元素依然保持是个 
        小堆，然后继续往下比较。
if (a[i] > a[0])
{
//交换
swap(&a[0], &a[i]);
//交换完后利用向下调整函数保持数组a中前k个元素依然是个小堆。
AdjustDown2(a, k, 0);//对堆顶元素a[0]进行向下调整
//继续往下比较
i++;
}
else//若堆顶元素a[0]比数组a剩余元素a[i]要大，则要继续往下比较。
i++;
}

//此时数组a中的前k个元素组成的小堆中的所有元素都是数组a中前k个最大的数，所以此时打印数 
    组a中前k个最大元素。
for (i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
//换行
printf("\n");
}

2.2.前K个最小的元素，建大堆。

(1)解决思路
  • 在原数组中使用数组的前K个元素建立一个大堆。
  • 遍历数组剩余的N-K个元素，并与堆顶元素比较。
  • 如果当前元素小于堆顶元素，则替换堆顶元素，替换后并对此时的堆顶元素进行向下调整，通过向下调整保持数组前K个元素依然是个大堆。
  • 当数组剩余的N-K个元素都遍历完了，则最终大堆中的元素即为所求的前K个最小元素(注意：这前K个最小元素不一定是有序的)。
(2)代码
//交换两个元素的函数
void swap(int* p1, int* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}


//建大堆的向下调整
void AdjustDown1(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;

while (child < n)
{
//让child始终指向当前双亲的左右孩子中最大一个孩子
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;
}

}

//TOP-K问题
//类型1：数据量N较小，可以全部加载到内存中。求数据量N的前K个最小的元素。
void PrintArrMinTopK(int* a, int n, int k)
{
// 1.用数组a中前k个元素建大堆来解决求N个数中最小的前K个元素。(注意：由于利用向下调整函 
    数建堆的时间复杂度是O(N)，所以我们使用向下调整函数来建)

int parent = 0;
for (parent = (k - 1 - 1) / 2; parent >= 0; parent--)
AdjustDown1(a, k, parent);

// 2.将数组a中剩余n-k个元素依次与堆顶元素进行比较，若剩余n-k个元素有比大堆堆顶元素小的 
    则这两个元素就交换。交换完后要保持数组a中前k个元素依然是个大堆。交换完后对此时的堆顶元 
    素(即数组首元素a[0])进行向下调整以此来要保持数组a中前k个元素依然是个大堆。

int cmp = n - k;//cmp表示比较次数。
int i = k;//下标i是用来遍历数组a中剩余n-k个元素的。
while (cmp--)
{
//(1)堆顶元素a[0]与数组a剩余的n-k个元素进行比较。
        //若堆顶元素a[0]比数组a剩余元素a[i]要大，则要交换且交换后数组前k个元素依然保持是个 
        大堆，然后继续往下比较。
if (a[i] < a[0])
{
//交换
swap(&a[0], &a[i]);
//交换完后利用向下调整函数保持数组a中前k个元素依然是个大堆。
AdjustDown1(a, k, 0);
//继续往下比较
i++;
}
else//若堆顶元素a[0]比数组a剩余元素a[i]要小，则要继续往下比较。
i++;
}

//此时数组a中的前k个元素组成的大堆中的所有元素都是数组a中前k个最小的数，所以此时打印数组a中前k个最小元素。
for (i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
//换行
printf("\n");
}

2.3.类型1的时间复杂度和空间复杂度的计算过程

(1)时间复杂度O(N * logK)
  • 利用向下调整函数把原数组初始化为堆（建堆）的时间复杂度是O(K)，因为只需要对前K个元素进行堆化。
  • 遍历剩余的N-K个元素与堆顶元素进行比较并判断是否要交换且最坏情况下要进行N-K次交换使得要对堆进行N-K次调整。每次调整堆的时间复杂度是O(logK)，因为堆的高度是logK，进而使得最坏情况下调整堆的时间复杂度是 O((N-K) * logK)。
  • 因此，总的时间复杂度是O(K) + O((N-K) * logK) = O(N * logK)。
(2)空间复杂度O(1)
  • 由于所有操作都是在原数组上进行的，除了几个用于临时交换的变量外，不需要额外的存储空间。
  • 因此，空间复杂度是O(1)。

注意： 论是求解前K个最大元素还是最小元素，时间复杂度和空间复杂度都是相同的。

3.类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。求数据量N的前K个最大的元素或者最小的元素。

3.1.求前K个最大的元素，建小堆。

图形解析：

(1)解决思路
  • 额外创建一个大小为K的数组minHeap。
  • 从文件中读取前K个元素存入数组minHeap中，并把数组minHeap构建成小堆。
  • 继续从文件中读取剩余的N-K个元素，并与堆顶元素比较。
  • 如果读取的文件数据val大于堆顶元素，则把读取到的文件数据val放置在堆顶位置，放置完后并对此时位于堆顶位置的文件数据val进行向下调整，通过向下调整保持数组minHeap中的K个元素依然是个小堆。
  • 当文件所有元素都读取完毕即读取到文件末尾时，则最终小堆(即数组minHeap)中的所有元素即为所求的前K个最大元素(注意：在数组minHeap中的前K个最大元素不一定是有序的)。
(2)代码
//交换两个元素的函数
void swap(int* p1, int* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}


//建小堆的向下调整
void AdjustDown2(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;

while (child < n)
{
//让child始终指向当前双亲的左右孩子中最小的那个孩子
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;
}

}


//类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。建小堆求数据量N的前K个最大的元素。
void PrintFileMaxTopK(const char* file, int k)//注意：指针file指向文件名(字符串)
{
//1.创建k个元素的数组minHeap
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
exit(-1);
}

//1.1.以只读的方式打开文件
FILE* pf = fopen(file, "r");

//1.2从文件pf中依次读取k个数据到数组minHeap中
for (int i = 0; i < k; ++i)
{
fscanf(pf, "%d", &minHeap[i]);
}

//2.利用向下调整函数把数组minHeap中的k个元素建成小堆
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown2(minHeap, k, i);
}

//val用来临时存放文件中读取的数据
int val = 0;

//3.将文件pf中剩余n-k个元素依次与数组minHeap的堆顶元素进行比较，若剩余n-k个元素有比小 
    堆堆顶元素大的数据val则这个读取到的文件数据val放在堆顶位置。放置后要保持数组minHeap中 
    的k个元素依然是个小堆。
//注意：此时文件指针指向文件第K+1个数据，所以此时从文件的第k+1个数据开始依次遍历文件中 
    的数据并把遍历到的数据用临时变量val存放起来，当遍历到的文件数据val比堆顶元素要大时则要 
    把val放到堆顶位置中，然后对val进行向下调整操作使得文件中大的数不断存放在小堆的下面。

    //利用while (fscanf(fout, "%d", &val) != EOF)不断一个一个读取文件pf中剩余n-k个元素。

while (fscanf(pf, "%d", &val) != EOF)
{
//3.1若遍历到的文件数据val比堆顶元素要大，则要把文件数据val放在堆顶位置中，并对此 
       时位于堆顶位置的文件数据val进行向下调整操作使得数组minHeap的k个元素依然保持是小堆。

if (val > minHeap[0])
{
minHeap[0] = val;//把文件数据val放在堆顶位置。
AdjustDown2(minHeap, k, 0);//把位于堆顶位置的文件数据val进行向下调整操作，进而 
                                       使得数组minHeap依然保持是个堆。
}
}

//此时数组minHeap中的k个元素就是文件存放的N个数据中的最大前K个元素。
//4.打印文件N个元素中前k个最大的数(即把数组minHeap中的所有元素打印出来)
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
printf("\n");


//关闭文件
fclose(pf);
}

3.2.前K个最小的元素，建大堆。

图形解析：

(1)解决思路
  • 额外创建一个大小为K的数组maxHeap。
  • 从文件中读取前K个元素存入数组a中，并把数组maxHeap构建成大堆。
  • 继续从文件中读取剩余的N-K个元素，并与堆顶元素比较。
  • 如果读取到的文件数据val小于堆顶元素，则把读取到的文件数据val放置到堆顶位置，放置完后并对此时位于堆顶位置的文件数据val进行向下调整，通过向下调整保持数组maxHeap中的K个元素依然是个大堆。
  • 当文件所有元素都读取完毕即读取到文件末尾时，则最终大堆(即数组maxHeap)中的所有元素即为所求的前K个最小元素(注意：在数组maxHeap中的前K个最小元素不一定是有序的)。
(2)代码
//交换两个元素的函数
void swap(int* p1, int* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}


//建大堆的向下调整
void AdjustDown1(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;

while (child < n)
{
//让child始终指向当前双亲的左右孩子中最大一个孩子
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;
}

}



//类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。建大堆求数据量N的前K个最小的元素。
void PrintFileMinTopK(const char* file, int k)//注意：指针file指向文件名字符串
{
//1.创建k个元素的数组maxHeap
int* maxHeap = (int*)malloc(sizeof(int) * k);
if (maxHeap == NULL)
{
perror("malloc fail");
exit(-1);
}

//1.1.以只读的方式打开文件
FILE* pf = fopen(file, "r");

//1.2.从文件pf中依次读取k个数据到数组maxHeap中
for (int i = 0; i < k; ++i)
{
fscanf(pf, "%d", &maxHeap[i]);
}

//2.利用向下调整函数把数组maxHeap中的k个元素建成大堆
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown1(maxHeap, k, i);
}

//val用来临时存放文件中读取的数据
int val = 0;

//3.将文件pf中剩余n-k个元素依次与数组maxHeap的堆顶元素进行比较，若剩余n-k个元素有比大 
    堆堆顶元素小的数据val则把这个读取到的文件数据val放置在堆顶位置，放置后保持数组maxHeap 
    中前k个元素依然是个大堆。
//注意：此时文件指针指向文件第k+1个数据，所以此时从文件的第k+1个数据开始依次遍历文件中 
    的数据并把遍历到的数据用临时变量val存放起来，当遍历到的文件数据val比堆顶元素要小时则要 
    把val放到堆顶中然后对val进行向下调整操作使得文件中小的数不断存放在大堆的下面。

   //利用while (fscanf(fout, "%d", &val) != EOF)不断一个一个读取文件pf中剩余n-k个元素。

while (fscanf(pf, "%d", &val) != EOF)
{
//3.1若遍历到的文件数据val比堆顶元素要小，则要把文件数据val放在堆顶位置中，并对位 
       于堆顶位置的文件数据val进行向下调整操作使得数组maxHeap中的k个元素依然保持是个大堆。

if (val < maxHeap[0])
{
maxHeap[0] = val;//把文件数据val放在堆顶位置。
AdjustDown1(maxHeap, k, 0);//把位于堆顶位置的文件数据val进行向下调整操作，进而 
                                       使得数组maxHeap依然保持是个大堆。
}
}

//此时数组maxHeap中的k个元素就是文件存放N个元素中的最小K个元素。
//4.打印文件N个元素中前k个最小的元素(即打印数组maxHeap中的所有元素)
for (int i = 0; i < k; ++i)
{
printf("%d ", maxHeap[i]);
}
printf("\n");

//关闭文件
fclose(pf);
}

3.3.类型2的时间复杂度和空间复杂度的计算过程

求解前K个最大元素的时间复杂度和空间复杂度：
(1)时间复杂度O(N * logK)
  • 读取前K个元素并利用向下调整函数构建小堆的时间复杂度是O(K)，因为需要对这K个元素进行堆化。
  • 接下来，需要遍历剩余的N-K个元素。
  • 对于每个元素：
    • 读取元素的时间复杂度是O(1)。
    • 如果元素大于堆顶元素，则替换堆顶元素，并进行一次向下调整，以维护小堆。向下调整的时间复杂度是O(logK)。
  • 因此，总的时间复杂度是O(K) + O((N-K) * logK) = O(N * logK)。
(2)空间复杂度O(K)
  • 需要一个大小为K的数组来存储堆中的元素。
  • 因此，空间复杂度是O(K)。

注意： 求解前K个最小元素的时间复杂度和空间复杂度的计算与求解前K个最大元素相同，因为算法的步骤和复杂度是一样的，只是构建的是大顶堆而不是小顶堆。

4.TOP-K问题的整个工程

4.1.TOP-K.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
#include <time.h>

//交换两个元素的函数
void swap(int* p1, int* p2);

//建堆的类型及所有建堆方式
//1.建大堆
//(1)建大堆的向上调整
void AdjustUp1(int* a, int child);

//(2)建大堆的向下调整
void AdjustDown1(int* a, int n, int parent);

//2.建小堆
//(1)建小堆的向上调整
void AdjustUp2(int* a, int child);

//(2)建小堆的向下调整
void AdjustDown2(int* a, int n, int parent);

//Tok问题
//类型1、N很小，内存中可以存到下N个数据。
//建小堆求数组N个数中最大的前K个元素
void PrintArrMaxTopK(int* a, int n, int k);

//建大堆求数组N个数中最小的前K个元素。
void PrintArrMinTopK(int* a, int n, int k);


//类型2、N很大，内存中存不下N个数据只能存在文件中。
//建小堆求文件N个数中最大的前K个元素。
void PrintFileMaxTopK(const char* file,int k);


//建大堆求文件N个数中最小的前K个元素。
void PrintFileMinTopK(const char* file, int k);

4.2.TOP-K.c

#include "TOP-K.h"

//交换两个元素的函数
void swap(int* p1, int* p2)
{
//判断指针p1与p2是否是空指针
assert(p1 && p2);
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}


//建堆的类型及所有建堆方式
//1.建大堆
//(1)建大堆的向上调整
void AdjustUp1(int* a, int child)
{
assert(a);
//找当前孩子的双亲
int parent = (child - 1) / 2;

while (child > 0)
{
if (a[child] > a[parent])//若当前孩子比自己的双亲还有大，则当前孩子就要进行向上调整。
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}

//(2)建大堆的向下调整
void AdjustDown1(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;

while (child < n)
{
//让child始终指向当前双亲的左右孩子中最大一个孩子
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;
}

}


//2.建小堆
//(1)建小堆的向上调整
void AdjustUp2(int* a, int child)
{
assert(a);
//找当前孩子的双亲
int parent = (child - 1) / 2;

while (child > 0)
{
if (a[child] < a[parent])//若当前孩子比自己的双亲还有小，则当前孩子就要进行向上调整
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}

//(2)建小堆的向下调整
void AdjustDown2(int* a, int n, int parent)
{
assert(a);
//找当前双亲的左孩子
int child = parent * 2 + 1;

while (child < n)
{
//让child始终指向当前双亲的左右孩子中最小的那个孩子
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;
}

}



//TOP-K问题
//类型1：数据量N较小，可以全部加载到内存中。建小堆求数据量N的前K个最大的元素。

void PrintArrMaxTopK(int* a, int n, int k)
{
// 1.用数组a中前k个元素建小堆来解决求N个数中最大的前K个元素。(注意：由于利用向下调整函 
    数建堆的时间复杂度是O(N)，所以我们使用向下调整函数来建堆)

int parent = 0;
for (parent = (k - 1 - 1) / 2; parent >= 0; parent--)
AdjustDown2(a, k, parent);

// 2.将数组a中剩余n-k个元素依次与堆顶元素进行比较，若剩余n-k个元素有比小堆堆顶元素大的 
    则这两个元素就交换。交换完后对此时的堆顶元素(即数组首元素a[0])进行向下调整以此来要保持 
    数组a中前k个元素依然是个小堆。

int cmp = n - k;//cmp表示比较次数。
int i = k;//下标i是用来遍历数组a中剩余n-k个元素的。
while (cmp--)
{
//(1)堆顶元素a[0]与数组a剩余的n-k个元素进行比较。
        //若堆顶元素a[0]比数组a剩余元素a[i]要小，则要交换且交换后数组前k个元素依然保持是个 
        小堆，然后继续往下比较。
if (a[i] > a[0])
{
//交换
swap(&a[0], &a[i]);
//交换完后利用向下调整函数保持数组a中前k个元素依然是个小堆。
AdjustDown2(a, k, 0);//对堆顶元素a[0]进行向下调整
//继续往下比较
i++;
}
else//若堆顶元素a[0]比数组a剩余元素a[i]要大，则要继续往下比较。
i++;
}

//此时数组a中的前k个元素组成的小堆中的所有元素都是数组a中前k个最大的数，所以此时打印数 
    组a中前k个最大元素。
for (i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
//换行
printf("\n");
}


//类型1：数据量N较小，可以全部加载到内存中。求数据量N的前K个最小的元素。
void PrintArrMinTopK(int* a, int n, int k)
{
// 1.用数组a中前k个元素建大堆来解决求N个数中最小的前K个元素。(注意：由于利用向下调整函 
    数建堆的时间复杂度是O(N)，所以我们使用向下调整函数来建)

int parent = 0;
for (parent = (k - 1 - 1) / 2; parent >= 0; parent--)
AdjustDown1(a, k, parent);

// 2.将数组a中剩余n-k个元素依次与堆顶元素进行比较，若剩余n-k个元素有比大堆堆顶元素小的 
    则这两个元素就交换。交换完后要保持数组a中前k个元素依然是个大堆。交换完后对此时的堆顶元 
    素(即数组首元素a[0])进行向下调整以此来要保持数组a中前k个元素依然是个大堆。

int cmp = n - k;//cmp表示比较次数。
int i = k;//下标i是用来遍历数组a中剩余n-k个元素的。
while (cmp--)
{
//(1)堆顶元素a[0]与数组a剩余的n-k个元素进行比较。
        //若堆顶元素a[0]比数组a剩余元素a[i]要大，则要交换且交换后数组前k个元素依然保持是个 
        大堆，然后继续往下比较。
if (a[i] < a[0])
{
//交换
swap(&a[0], &a[i]);
//交换完后利用向下调整函数保持数组a中前k个元素依然是个大堆。
AdjustDown1(a, k, 0);
//继续往下比较
i++;
}
else//若堆顶元素a[0]比数组a剩余元素a[i]要小，则要继续往下比较。
i++;
}

//此时数组a中的前k个元素组成的大堆中的所有元素都是数组a中前k个最小的数，所以此时打印数组a中前k个最小元素。
for (i = 0; i < k; i++)
{
printf("%d ", a[i]);
}
//换行
printf("\n");
}


//类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。建小堆求数据量N的前K个最大的元素。
void PrintFileMaxTopK(const char* file, int k)//注意：指针file指向文件名(字符串)
{
//1.创建k个元素的数组minHeap
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
exit(-1);
}

//1.1.以只读的方式打开文件
FILE* pf = fopen(file, "r");

//1.2从文件pf中依次读取k个数据到数组minHeap中
for (int i = 0; i < k; ++i)
{
fscanf(pf, "%d", &minHeap[i]);
}

//2.利用向下调整函数把数组minHeap中的k个元素建成小堆
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown2(minHeap, k, i);
}

//val用来临时存放文件中读取的数据
int val = 0;

//3.将文件pf中剩余n-k个元素依次与数组minHeap的堆顶元素进行比较，若剩余n-k个元素有比小 
    堆堆顶元素大的数据val则这个读取到的文件数据val放在堆顶位置。放置后要保持数组minHeap中 
    的k个元素依然是个小堆。
//注意：此时文件指针指向文件第K+1个数据，所以此时从文件的第k+1个数据开始依次遍历文件中 
    的数据并把遍历到的数据用临时变量val存放起来，当遍历到的文件数据val比堆顶元素要大时则要 
    把val放到堆顶位置中，然后对val进行向下调整操作使得文件中大的数不断存放在小堆的下面。

    //利用while (fscanf(fout, "%d", &val) != EOF)不断一个一个读取文件pf中剩余n-k个元素。

while (fscanf(pf, "%d", &val) != EOF)
{
//3.1若遍历到的文件数据val比堆顶元素要大，则要把文件数据val放在堆顶位置中，并对此 
       时位于堆顶位置的文件数据val进行向下调整操作使得数组minHeap的k个元素依然保持是小堆。

if (val > minHeap[0])
{
minHeap[0] = val;//把文件数据val放在堆顶位置。
AdjustDown2(minHeap, k, 0);//把位于堆顶位置的文件数据val进行向下调整操作，进而 
                                       使得数组minHeap依然保持是个堆。
}
}

//此时数组minHeap中的k个元素就是文件存放的N个数据中的最大前K个元素。
//4.打印文件N个元素中前k个最大的数(即把数组minHeap中的所有元素打印出来)
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
printf("\n");


//关闭文件
fclose(pf);
}




//类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。建大堆求数据量N的前K个最小的元素。
void PrintFileMinTopK(const char* file, int k)//注意：指针file指向文件名字符串
{
//1.创建k个元素的数组maxHeap
int* maxHeap = (int*)malloc(sizeof(int) * k);
if (maxHeap == NULL)
{
perror("malloc fail");
exit(-1);
}

//1.1.以只读的方式打开文件
FILE* pf = fopen(file, "r");

//1.2.从文件pf中依次读取k个数据到数组maxHeap中
for (int i = 0; i < k; ++i)
{
fscanf(pf, "%d", &maxHeap[i]);
}

//2.利用向下调整函数把数组maxHeap中的k个元素建成大堆
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown1(maxHeap, k, i);
}

//val用来临时存放文件中读取的数据
int val = 0;

//3.将文件pf中剩余n-k个元素依次与数组maxHeap的堆顶元素进行比较，若剩余n-k个元素有比大 
    堆堆顶元素小的数据val则把这个读取到的文件数据val放置在堆顶位置，放置后保持数组maxHeap 
    中前k个元素依然是个大堆。
//注意：此时文件指针指向文件第k+1个数据，所以此时从文件的第k+1个数据开始依次遍历文件中 
    的数据并把遍历到的数据用临时变量val存放起来，当遍历到的文件数据val比堆顶元素要小时则要 
    把val放到堆顶中然后对val进行向下调整操作使得文件中小的数不断存放在大堆的下面。

   //利用while (fscanf(fout, "%d", &val) != EOF)不断一个一个读取文件pf中剩余n-k个元素。

while (fscanf(pf, "%d", &val) != EOF)
{
//3.1若遍历到的文件数据val比堆顶元素要小，则要把文件数据val放在堆顶位置中，并对位 
       于堆顶位置的文件数据val进行向下调整操作使得数组maxHeap中的k个元素依然保持是个大堆。

if (val < maxHeap[0])
{
maxHeap[0] = val;//把文件数据val放在堆顶位置。
AdjustDown1(maxHeap, k, 0);//把位于堆顶位置的文件数据val进行向下调整操作，进而 
                                       使得数组maxHeap依然保持是个大堆。
}
}

//此时数组maxHeap中的k个元素就是文件存放N个元素中的最小K个元素。
//4.打印文件N个元素中前k个最小的元素(即打印数组maxHeap中的所有元素)
for (int i = 0; i < k; ++i)
{
printf("%d ", maxHeap[i]);
}
printf("\n");

//关闭文件
fclose(pf);
}

4.3.test.c测试函数

#include "TOP-K.h"

void Print(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
//换行
printf("\n");
}

//类型1测试
void TestPrintArrMaxTopK()
{
int n = 100;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
perror("malloc fail");
exit(-1);
}
srand((unsigned int)time(NULL));

//产生1万个随机值
int i = 0;
for (i = 0; i < n; ++i)
{
//注意：rand函数产生随机值的范围是0 ~ 32767。
a[i] = rand() % 10000 + 1;//随机值的范围1~10000
}

//把数组a中的10个元素改成10001 ~ 10010。这样做的目的是：测试PrintArrMaxTopK函数是否正 
    确找出数组a中最大的10个元素。
a[5] = 10000 + 1;
a[12] = 10000 + 2;
a[53] = 10000 + 3;
a[98] = 10000 + 4;
a[15] = 10000 + 5;
a[35] = 10000 + 6;
a[99] = 10000 + 7;
a[76] = 10000 + 8;
a[43] = 10000 + 9;
a[66] = 10000 + 10;
//打印
Print(a, n);
printf("\n");

//找出n个数中前k = 10个最大的数，并打印前k = 10个最大的数。
PrintArrMaxTopK(a, n, 10);
printf("\n");
//打印整个数组a
Print(a, n);
printf("\n");

//释放动态数组a
free(a);
a = NULL;
}

void TestPrintArrMinTopK()
{
int n = 100;
int* a = (int*)malloc(sizeof(int) * n);
if (a == NULL)
{
perror("malloc fail");
exit(-1);
}
srand((unsigned int)time(NULL));

//产生1万个随机值
int i = 0;
for (i = 0; i < n; ++i)
{
//注意：rand函数产生随机值的范围是0 ~ 32767。
a[i] = rand() % 10000 + 11;//随机值的范围1~10000
}

//把数组a中的10个元素改成1 ~ 10。这样做的目的是：测试PrintArrMinTopK函数是否正确找出数 
    组a中最小的10个元素。
a[5] = 1;
a[12] = 2;
a[53] = 3;
a[98] = 4;
a[15] = 5;
a[35] = 6;
a[99] = 7;
a[76] = 8;
a[43] = 9;
a[66] = 10;
//打印
Print(a, n);
printf("\n");


//找出n个数中前k = 10个最小的数，并打印前k = 10个最小的数。
PrintArrMinTopK(a, n, 10);
printf("\n");
//打印整个数组
Print(a, n);
printf("\n");

//释放动态数组a
free(a);
a = NULL;
}

//类型2测试
//生成随机N个数据的文件+解决Tok问题：找N个数中前K个最大的数。
void TestPrintFileMaxTopK()
{
//一、写n个数据进文件中
int n, k;//n表示文件中的数据个数，k表示文件n个数中最大前k个的数
printf("请输入n和k:>");
//1.输入n、k
scanf("%d%d", &n, &k);

//2.打开文件data.txt
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}

//3.把n个数写入文件data.txt中
//(1)随机生成n-k个数据并把这n-k个数据写入指针fin指向的文件data.txt中。
int i = 0;
for (i = 0; i < n - k; i++)
{
int val = rand() % 10000 + 1;//产生随机数的范围1 ~ 10000
fprintf(fin, "%d\n", val);
}

//(2)把k个数据写入指针fin指向的文件data.txt中。
for (i = 10001; i < 10001 + k; i++)
fprintf(fin, "%d\n", i);

//关闭文件data.txt
fclose(fin);

//二、创建k个元素大小的小堆来解决topk问题
PrintFileMaxTopK("data.txt", k);

}


//生成随机N个数据的文件+解决Tok问题：找N个数中前K个最小的数。
void TestPrintFileMinTopK()
{
//一、写n个数据进文件中
int n, k;//n表示文件中的数据个数，k表示文件n个数中最大前k个的数
printf("请输入n和k:>");
//1.输入n、k
scanf("%d%d", &n, &k);

//2.打开文件
FILE* fin = fopen("data.txt", "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}

//3.把n个数写入文件data.txt中
//(1)随机生成n-k个数据并把这n-k个数据写入指针fin指向的文件data.txt中。
int i = 0;
for (i = 0; i < n - k; i++)
{
int val = rand() % 10000 + 11;//产生随机数的范围11 ~ 10011
fprintf(fin, "%d\n", val);
}

//(2)把k个数据写入指针fin指向的文件data.txt中。
for (i = 1; i <= k; i++)
fprintf(fin, "%d\n", i);

//关闭文件
fclose(fin);

//二、创建k个元素大小的大堆来解决topk问题
PrintFileMinTopK("data.txt", k);//注意："data.txt"是文件名字符串
}

int main()
{
srand((size_t)time(NULL));
//类型1的测试用例
//TestPrintArrMaxTopK();
TestPrintArrMinTopK();

//类型2的测试用例
//TestPrintFileMaxTopK();
//TestPrintFileMinTopK();

return 0;
}


原文地址：https://blog.csdn.net/2302_76314368/article/details/142733264

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024