TOP-K问题

目录

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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/440837.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

2024 ciscn WP

2024 ciscn WP

一、MISC 1.火锅链观光打卡 打开后连接自己的钱包&#xff0c;然后点击开始游戏&#xff0c;答题八次后点击获取NFT&#xff0c;得到有flag的图片 没什么多说的&#xff0c;知识问答题 兑换 NFT Flag{y0u_ar3_hotpot_K1ng} 2.Power Trajectory Diagram 方法1&#xff1a; 使用p…
阅读更多...
集合论基础 - 离散数学系列（一）

集合论基础 - 离散数学系列（一）

目录 1. 集合的基本概念 什么是集合&#xff1f; 集合的表示方法 常见的特殊集合 2. 子集与幂集 子集 幂集 3. 集合的运算 交集、并集与补集 集合运算规则 4. 笛卡尔积 5. 实际应用 6. 例题与练习 例题1 练习题 总结 引言 集合论是离散数学的基础之一&#xff…
阅读更多...
Linux 外设驱动 应用 1 IO口输出

Linux 外设驱动 应用 1 IO口输出

从这里开始外设驱动介绍&#xff0c;这里使用的IMX8的芯片作为驱动介绍 开发流程&#xff1a; 修改设备树&#xff0c;配置 GPIO1_IO07 为 GPIO 输出。使用 sysfs 接口或编写驱动程序控制 GPIO 引脚。编译并测试。 这里假设设备树&#xff0c;已经配置好了。不在论述这个问题…
阅读更多...
金融教育宣传月 | 平安养老险百色中心支公司开展金融知识“消保县域行”宣传活动

金融教育宣传月 | 平安养老险百色中心支公司开展金融知识“消保县域行”宣传活动

9月22日&#xff0c;平安养老险百色中心支公司积极落实国家金融监督管理总局关于开展金融教育宣传月活动的相关要求&#xff0c;联合平安人寿百色中心支公司共同组成了平安志愿者小队&#xff0c;走进百色市四塘镇百兰村开展了一场别开生面的金融消费者权益保护宣传活动。此次活…
阅读更多...
通用mybatis-plus查询封装(QueryGenerator)

通用mybatis-plus查询封装(QueryGenerator)

结果如下图所示 java类代码分别如下 1 package com.hdx.contractor.util.mybatis;import com.hdx.contractor.common.user.SecurityUser; import com.hdx.contractor.common.user.UserDetail; import com.hdx.contractor.util.query.oConvertUtils; import lombok.extern.slf…
阅读更多...
YOLO11改进|卷积篇|引入线性可变形卷积LDConv

YOLO11改进|卷积篇|引入线性可变形卷积LDConv

目录 一、【LDConv】卷积1.1【LDConv】卷积介绍1.2【LDConv】核心代码 二、添加【LDConv】卷积2.1STEP12.2STEP22.3STEP32.4STEP4 三、yaml文件与运行3.1yaml文件3.2运行成功截图 一、【LDConv】卷积 1.1【LDConv】卷积介绍 下图是【LDCNV】的结构图&#xff0c;让我们简单分析…
阅读更多...
Ajax面试题：（第一天）

Ajax面试题：（第一天）

目录 1.说一下网络模型 2.在浏览器地址栏键入URL&#xff0c;按下回车之后会经历以下流程&#xff1a; 3.什么是三次握手和四次挥手&#xff1f; 4.http协议和https协议的区别 1.说一下网络模型 注&#xff1a;各层含义按自己理解即可 2.在浏览器地址栏键入URL&#xff0c;…
阅读更多...
盲拍合约：让竞拍更公平与神秘的创新解决方案

盲拍合约：让竞拍更公平与神秘的创新解决方案

目录 前言 一、盲拍合约是什么&#xff1f; 二、盲拍合约工作原理 1、合约创建与初始化 2、用户出价&#xff08;Bid&#xff09; 3、出价结束 4、披露出价&#xff08;Reveal&#xff09; 5、处理最高出价 6、结束拍卖 7、退款与提款 三、解析盲拍合约代码…
阅读更多...
阿里云域名解析和备案

阿里云域名解析和备案

文章目录 1、域名解析2、新手引导3、ICP备案 1、域名解析 2、新手引导 3、ICP备案
阅读更多...
类的特殊成员函数——三之法则、五之法则、零之法则

类的特殊成员函数——三之法则、五之法则、零之法则

系统中的动态资源、文件句柄&#xff08;socket描述符、文件描述符&#xff09;是有限的&#xff0c;在类中若涉及对此类资源的操作&#xff0c;但是未做到妥善的管理&#xff0c;常会造成资源泄露问题&#xff0c;严重的可能造成资源不可用&#xff0c;如申请内存失败、文件句…
阅读更多...
【redis-05】redis保证和mysql数据一致性

【redis-05】redis保证和mysql数据一致性

redis系列整体栏目 内容链接地址【一】redis基本数据类型和使用场景https://zhenghuisheng.blog.csdn.net/article/details/142406325【二】redis的持久化机制和原理https://zhenghuisheng.blog.csdn.net/article/details/142441756【三】redis缓存穿透、缓存击穿、缓存雪崩htt…
阅读更多...
57.对称二叉树

57.对称二叉树

迭代 class Solution {public boolean isSymmetric(TreeNode root) {if(rootnull){return true;}Deque<TreeNode> denew LinkedList<>();TreeNode l,r;int le;de.offer(root.left);de.offer(root.right);while(!de.isEmpty()){lde.pollFirst();rde.pollLast();if(…
阅读更多...
BMC pam认证的使用

BMC pam认证的使用

1.说明 1.1 文档参考资料 https://www.chiark.greenend.org.uk/doc/libpam-doc/html/Linux-PAM_ADG.htmlhttp://www.fifi.org/doc/libpam-doc/html/pam_appl-3.htmlpdf文档: https://fossies.org/linux/Linux-PAM-docs/doc/adg/Linux-PAM_ADG.pdflinux-pam 中文文档pam 旧文p…
阅读更多...
＜数据集＞工程机械识别数据集＜目标检测＞

＜数据集＞工程机械识别数据集＜目标检测＞

数据集格式&#xff1a;VOCYOLO格式 图片数量&#xff1a;2644张 标注数量(xml文件个数)&#xff1a;2644 标注数量(txt文件个数)&#xff1a;2644 标注类别数&#xff1a;3 标注类别名称&#xff1a;[dump truck, wheel loader, excavators] 序号类别名称图片数框数1dum…
阅读更多...
SpringBootWeb快速入门！详解如何创建一个简单的SpringBoot项目？

SpringBootWeb快速入门！详解如何创建一个简单的SpringBoot项目？

在现代Web开发中&#xff0c;SpringBoot以其简化的配置和快速的开发效率而受到广大开发者的青睐。本篇文章将带领你从零开始&#xff0c;搭建一个基于SpringBoot的简单Web应用~ 一、前提准备 想要创建一个SpringBoot项目&#xff0c;需要做如下准备&#xff1a; idea集成开发…
阅读更多...
wordpress Contact form 7发件人邮箱设置

wordpress Contact form 7发件人邮箱设置

此教程仅适用于演示站有留言的主题&#xff0c;演示站没有留言的主题&#xff0c;就别往下看了&#xff0c;免费浪费时间。 使用了Contact form 7插件的简站WordPress主题&#xff0c;在有人留言时&#xff0c;就会发邮件到网站的系统邮箱(一般与管理员邮箱为同一个)里。上面显…
阅读更多...
SpringCloud简介 Ribbon Eureka 远程调用RestTemplate类 openfeign

SpringCloud简介 Ribbon Eureka 远程调用RestTemplate类 openfeign

〇、SpringCloud 0.区别于单体项目和soa架构&#xff0c;微服务架构每个服务独立&#xff0c;灵活。 1. spring cloud是一个完整的微服务框架&#xff0c;springCloud包括三个体系&#xff1a; spring cloud Netflix spring cloud Alibaba spring 其他 2.spring cloud 版本命名…
阅读更多...
论文阅读笔记-LogME: Practical Assessment of Pre-trained Models for Transfer Learning

论文阅读笔记-LogME: Practical Assessment of Pre-trained Models for Transfer Learning

前言 在NLP领域，预训练模型（准确的说应该是预训练语言模型）似乎已经成为各大任务必备的模块了，经常有看到文章称后BERT时代或后XXX时代，分析对比了许多主流模型的优缺点，这些相对而言有些停留在理论层面，可是有时候对于手上正在解决的任务，要用到预训练语言模型时，面…
阅读更多...
软件设计师（软考学习）

软件设计师（软考学习）

数据库技术 数据库基础知识 1. 数据库中的简单属性、多值属性、复合属性、派生属性简单属性&#xff1a;指不能够再分解成更小部分的属性&#xff0c;通常是数据表中的一个列。例如学生表中的“学号”、“姓名”等均为简单属性。 多值属性&#xff1a;指一个属性可以有多个值…
阅读更多...
sql-labs：42~65

sql-labs：42~65

less42&#xff08;单引号闭合、报错回显&#xff09; login_useradmin login_password123 and if(11,sleep(2),1) # # 单引号闭合 ​ login_useradmin login_password123and updatexml(1,concat(0x7e,database(),0x7e),1)# # 报错回显…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023