目录

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;}elsebreak;}}//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;}elsebreak;}}//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;}elsebreak;}}//类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。建小堆求数据量N的前K个最大的元素。
void PrintFileMaxTopK(const char* file, int k)//注意：指针file指向文件名(字符串)
{//1.创建k个元素的数组minHeapint* 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;}elsebreak;}}//类型2：数据量N很大无法全部加载到内存中只能存进硬盘文件。建大堆求数据量N的前K个最小的元素。
void PrintFileMinTopK(const char* file, int k)//注意：指针file指向文件名字符串
{//1.创建k个元素的数组maxHeapint* 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;}elsebreak;}
}//(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;}elsebreak;}}//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;}elsebreak;}
}//(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;}elsebreak;}}//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个元素的数组minHeapint* 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个元素的数组maxHeapint* 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");//打印整个数组aPrint(a, n);printf("\n");//释放动态数组afree(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");//释放动态数组afree(a);a = NULL;
}//类型2测试
//生成随机N个数据的文件+解决Tok问题：找N个数中前K个最大的数。
void TestPrintFileMaxTopK()
{//一、写n个数据进文件中int n, k;//n表示文件中的数据个数，k表示文件n个数中最大前k个的数printf("请输入n和k:>");//1.输入n、kscanf("%d%d", &n, &k);//2.打开文件data.txtFILE* 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 ~ 10000fprintf(fin, "%d\n", val);}//(2)把k个数据写入指针fin指向的文件data.txt中。for (i = 10001; i < 10001 + k; i++)fprintf(fin, "%d\n", i);//关闭文件data.txtfclose(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、kscanf("%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 ~ 10011fprintf(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;
}