目录
堆的建立
向上调整建堆
向下调整建堆
向上调整和向下调整时间复杂度的比较
大小堆如何选择
Top-K问题
之前我们实现的堆是创建一个数组,将元素组的内容拷贝过来进行排序的,这样的空间复杂度是O(N),我们可对堆进行优化,使得不拷贝元素,直接在原数组上进行操作使得原数组变为有序的数组
堆的建立
向上调整建堆
//建堆——向上调整建堆 第一个元素看作一个堆,后面的元素看作依次插入
for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);
}
向下调整建堆
之前向下调整的建堆方法是,头尾交换然后将头向下调整,向下调整的前提是左右子树都是大堆或小堆
当数组是这个样子。就无法使用向下调整
我们可以从倒数第一个非叶子节点(倒数第一个叶子节点的父节点)开始向下开始调,直到调整到根,叶子节点没必要调(兄弟关系),
先让i指向60,然后60和70交换,i--,i指向100再进行调整,之后再i--,i等于100进行调整
//建堆——向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点
//物理上操作数组,逻辑上在操作堆
{
AdjusuDown(a, n, i);
}
向上调整和向下调整时间复杂度的比较
向下调整时间复杂度:O(N)
向下调整总步数=该层个数*需向下调整次数
当满二叉树节点较多时,最后一层节点的个数约为总结点个数的一半,向下调整的好处:节点所在层数越小(以第1层为比较基准),调整次数越多,节点所在层数越大,此时节点越多,调整次数越小
向上调整时间复杂度:O(N*logN)
利用错位相减可计算出调整次数
我们只算最后一层的调整次数
向上调整:越往下节点越多,调整次数越多,算法时间复杂度过大
大小堆如何选择
对于升序和降序我们该如何选择建堆方式?
答案:1.升序——大堆 2.降序——小堆
大思路:选择排序,依次选数,从后往前排
升序建小堆会出问题
建堆的时间复杂度是O(N),效率低
选数
//选数
int i = 0;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjusuDown(a, n - i, 0);
++i;
}
void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent)
{
HPDataTypedef minChild = parent * 2 + 1;
while (minChilda[minChild])
{
minChild++;
}
if (a[minChild] > a[parent])
{
Swap(&a[parent], &a[minChild]);
parent = minChild;
minChild = parent * 2 + 1;
}
else
break;
}
}
void Heapsort(int* a, int n)
{
//建堆——向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点
//物理上操作数组,逻辑上在操作堆
{
AdjusuDown(a, n, i);
}
//选数
int i = 1;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjusuDown(a, n - i, 0);
++i;
}
}
int main()
{
int a[] = { 65,100,75,32,50,60 };
Heapsort(a, 6);
return 0;
}
Top-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素
找前K个最大的
1.排序——O(N*logN)
2.堆选数
a.建大堆和建小堆都可以,建大堆相当于选K次(Pop k次)时间复杂度:O(N+logN*k)
更好的方式,建小堆
1.用前K个数,建K个数的小堆
2.依次遍历后续的N-k个数,如果比堆里的数据大,就替换堆里的数据,然后向下替换
,堆里的数据就是最大的前K个
时间复杂度:K+logK*(N-K),综合之后O(N),空间复杂度O(K)
以文件方式进行操作(这里数组大小为10,K=10)
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
// 如何读取前K个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
}
// 建k个数小堆
for (int j = (k - 2) / 2; j >= 0; --j)
{
AdjusuDown(minHeap, k, j);
}
// 继续读取后N-K
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjusuDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.txt";
int N = 10000;
int K = 10;
//CreateDataFile(filename, N);
PrintTopK(filename, K);
return 0;
}
void CreateDataFile(const char* filename, int N)
{
FILE* fin = fopen(filename, "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
srand(time(0));
for (int i = 0; i < N; ++i)
{
fprintf(fin, "%dn", rand() % 1000000);
}
fclose(fin);
}
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
// 如何读取前K个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
}
// 建k个数小堆
for (int j = (k - 2) / 2; j >= 0; --j)//(k-1-1)/2
{
AdjusuDown(minHeap, k, j);
}
// 继续读取后N-K
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjusuDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.txt";
int N = 10000;
int K = 10;
CreateDataFile(filename, N);//
PrintTopK(filename, K);
return 0;
}
//建堆——向上调整建堆 第一个元素看作一个堆,后面的元素看作依次插入 for (int i = 1; i < n; ++i) { AdjustUp(a, i); }
向下调整建堆
之前向下调整的建堆方法是,头尾交换然后将头向下调整,向下调整的前提是左右子树都是大堆或小堆
当数组是这个样子。就无法使用向下调整
我们可以从倒数第一个非叶子节点(倒数第一个叶子节点的父节点)开始向下开始调,直到调整到根,叶子节点没必要调(兄弟关系),
先让i指向60,然后60和70交换,i--,i指向100再进行调整,之后再i--,i等于100进行调整
//建堆——向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点
//物理上操作数组,逻辑上在操作堆
{
AdjusuDown(a, n, i);
}
向上调整和向下调整时间复杂度的比较
向下调整时间复杂度:O(N)
向下调整总步数=该层个数*需向下调整次数
当满二叉树节点较多时,最后一层节点的个数约为总结点个数的一半,向下调整的好处:节点所在层数越小(以第1层为比较基准),调整次数越多,节点所在层数越大,此时节点越多,调整次数越小
向上调整时间复杂度:O(N*logN)
利用错位相减可计算出调整次数
我们只算最后一层的调整次数
向上调整:越往下节点越多,调整次数越多,算法时间复杂度过大
大小堆如何选择
对于升序和降序我们该如何选择建堆方式?
答案:1.升序——大堆 2.降序——小堆
大思路:选择排序,依次选数,从后往前排
升序建小堆会出问题
建堆的时间复杂度是O(N),效率低
选数
//选数
int i = 0;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjusuDown(a, n - i, 0);
++i;
}
void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent)
{
HPDataTypedef minChild = parent * 2 + 1;
while (minChilda[minChild])
{
minChild++;
}
if (a[minChild] > a[parent])
{
Swap(&a[parent], &a[minChild]);
parent = minChild;
minChild = parent * 2 + 1;
}
else
break;
}
}
void Heapsort(int* a, int n)
{
//建堆——向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点
//物理上操作数组,逻辑上在操作堆
{
AdjusuDown(a, n, i);
}
//选数
int i = 1;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjusuDown(a, n - i, 0);
++i;
}
}
int main()
{
int a[] = { 65,100,75,32,50,60 };
Heapsort(a, 6);
return 0;
}
Top-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素
找前K个最大的
1.排序——O(N*logN)
2.堆选数
a.建大堆和建小堆都可以,建大堆相当于选K次(Pop k次)时间复杂度:O(N+logN*k)
更好的方式,建小堆
1.用前K个数,建K个数的小堆
2.依次遍历后续的N-k个数,如果比堆里的数据大,就替换堆里的数据,然后向下替换
,堆里的数据就是最大的前K个
时间复杂度:K+logK*(N-K),综合之后O(N),空间复杂度O(K)
以文件方式进行操作(这里数组大小为10,K=10)
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
// 如何读取前K个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
}
// 建k个数小堆
for (int j = (k - 2) / 2; j >= 0; --j)
{
AdjusuDown(minHeap, k, j);
}
// 继续读取后N-K
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjusuDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.txt";
int N = 10000;
int K = 10;
//CreateDataFile(filename, N);
PrintTopK(filename, K);
return 0;
}
void CreateDataFile(const char* filename, int N)
{
FILE* fin = fopen(filename, "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
srand(time(0));
for (int i = 0; i < N; ++i)
{
fprintf(fin, "%dn", rand() % 1000000);
}
fclose(fin);
}
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
// 如何读取前K个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
}
// 建k个数小堆
for (int j = (k - 2) / 2; j >= 0; --j)//(k-1-1)/2
{
AdjusuDown(minHeap, k, j);
}
// 继续读取后N-K
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjusuDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.txt";
int N = 10000;
int K = 10;
CreateDataFile(filename, N);//
PrintTopK(filename, K);
return 0;
}
之前向下调整的建堆方法是,头尾交换然后将头向下调整,向下调整的前提是左右子树都是大堆或小堆
当数组是这个样子。就无法使用向下调整
我们可以从倒数第一个非叶子节点(倒数第一个叶子节点的父节点)开始向下开始调,直到调整到根,叶子节点没必要调(兄弟关系),
先让i指向60,然后60和70交换,i--,i指向100再进行调整,之后再i--,i等于100进行调整
//建堆——向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点 //物理上操作数组,逻辑上在操作堆 { AdjusuDown(a, n, i); }
向下调整时间复杂度:O(N)
向下调整总步数=该层个数*需向下调整次数
当满二叉树节点较多时,最后一层节点的个数约为总结点个数的一半,向下调整的好处:节点所在层数越小(以第1层为比较基准),调整次数越多,节点所在层数越大,此时节点越多,调整次数越小
向上调整时间复杂度:O(N*logN)
利用错位相减可计算出调整次数
我们只算最后一层的调整次数
向上调整:越往下节点越多,调整次数越多,算法时间复杂度过大
大小堆如何选择
对于升序和降序我们该如何选择建堆方式?
答案:1.升序——大堆 2.降序——小堆
大思路:选择排序,依次选数,从后往前排
升序建小堆会出问题
建堆的时间复杂度是O(N),效率低
选数
//选数
int i = 0;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjusuDown(a, n - i, 0);
++i;
}
void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent)
{
HPDataTypedef minChild = parent * 2 + 1;
while (minChilda[minChild])
{
minChild++;
}
if (a[minChild] > a[parent])
{
Swap(&a[parent], &a[minChild]);
parent = minChild;
minChild = parent * 2 + 1;
}
else
break;
}
}
void Heapsort(int* a, int n)
{
//建堆——向下调整建堆
for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点
//物理上操作数组,逻辑上在操作堆
{
AdjusuDown(a, n, i);
}
//选数
int i = 1;
while (i < n)
{
Swap(&a[0], &a[n - i]);
AdjusuDown(a, n - i, 0);
++i;
}
}
int main()
{
int a[] = { 65,100,75,32,50,60 };
Heapsort(a, 6);
return 0;
}
Top-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素
找前K个最大的
1.排序——O(N*logN)
2.堆选数
a.建大堆和建小堆都可以,建大堆相当于选K次(Pop k次)时间复杂度:O(N+logN*k)
更好的方式,建小堆
1.用前K个数,建K个数的小堆
2.依次遍历后续的N-k个数,如果比堆里的数据大,就替换堆里的数据,然后向下替换
,堆里的数据就是最大的前K个
时间复杂度:K+logK*(N-K),综合之后O(N),空间复杂度O(K)
以文件方式进行操作(这里数组大小为10,K=10)
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
// 如何读取前K个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
}
// 建k个数小堆
for (int j = (k - 2) / 2; j >= 0; --j)
{
AdjusuDown(minHeap, k, j);
}
// 继续读取后N-K
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjusuDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.txt";
int N = 10000;
int K = 10;
//CreateDataFile(filename, N);
PrintTopK(filename, K);
return 0;
}
void CreateDataFile(const char* filename, int N)
{
FILE* fin = fopen(filename, "w");
if (fin == NULL)
{
perror("fopen fail");
return;
}
srand(time(0));
for (int i = 0; i < N; ++i)
{
fprintf(fin, "%dn", rand() % 1000000);
}
fclose(fin);
}
void PrintTopK(const char* filename, int k)
{
assert(filename);
FILE* fout = fopen(filename, "r");
if (fout == NULL)
{
perror("fopen fail");
return;
}
int* minHeap = (int*)malloc(sizeof(int) * k);
if (minHeap == NULL)
{
perror("malloc fail");
return;
}
// 如何读取前K个数据
for (int i = 0; i < k; ++i)
{
fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行
}
// 建k个数小堆
for (int j = (k - 2) / 2; j >= 0; --j)//(k-1-1)/2
{
AdjusuDown(minHeap, k, j);
}
// 继续读取后N-K
int val = 0;
while (fscanf(fout, "%d", &val) != EOF)
{
if (val > minHeap[0])
{
minHeap[0] = val;
AdjusuDown(minHeap, k, 0);
}
}
for (int i = 0; i < k; ++i)
{
printf("%d ", minHeap[i]);
}
free(minHeap);
fclose(fout);
}
int main()
{
const char* filename = "Data.txt";
int N = 10000;
int K = 10;
CreateDataFile(filename, N);//
PrintTopK(filename, K);
return 0;
}
对于升序和降序我们该如何选择建堆方式?
答案:1.升序——大堆 2.降序——小堆
大思路:选择排序,依次选数,从后往前排
升序建小堆会出问题
建堆的时间复杂度是O(N),效率低
选数
//选数 int i = 0; while (i < n) { Swap(&a[0], &a[n - i]); AdjusuDown(a, n - i, 0); ++i; }
void AdjusuDown(HPDataTypedef* a,int n, HPDataTypedef parent) { HPDataTypedef minChild = parent * 2 + 1; while (minChilda[minChild]) { minChild++; } if (a[minChild] > a[parent]) { Swap(&a[parent], &a[minChild]); parent = minChild; minChild = parent * 2 + 1; } else break; } } void Heapsort(int* a, int n) { //建堆——向下调整建堆 for (int i = (n - 1 - 1) / 2; i >= 0; --i) //n-1是最后一个节点,(n-1-1)/2是最后一个节点的父节点 //物理上操作数组,逻辑上在操作堆 { AdjusuDown(a, n, i); } //选数 int i = 1; while (i < n) { Swap(&a[0], &a[n - i]); AdjusuDown(a, n - i, 0); ++i; } } int main() { int a[] = { 65,100,75,32,50,60 }; Heapsort(a, 6); return 0; }
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
1. 用数据集合中前K个元素来建堆
前k个最大的元素,则建小堆
前k个最小的元素,则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素
找前K个最大的1.排序——O(N*logN)
2.堆选数
a.建大堆和建小堆都可以,建大堆相当于选K次(Pop k次)时间复杂度:O(N+logN*k)
更好的方式,建小堆
1.用前K个数,建K个数的小堆
2.依次遍历后续的N-k个数,如果比堆里的数据大,就替换堆里的数据,然后向下替换
,堆里的数据就是最大的前K个
时间复杂度:K+logK*(N-K),综合之后O(N),空间复杂度O(K)
以文件方式进行操作(这里数组大小为10,K=10)
void PrintTopK(const char* filename, int k) { assert(filename); FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); return; } int* minHeap = (int*)malloc(sizeof(int) * k); if (minHeap == NULL) { perror("malloc fail"); return; } // 如何读取前K个数据 for (int i = 0; i < k; ++i) { fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行 } // 建k个数小堆 for (int j = (k - 2) / 2; j >= 0; --j) { AdjusuDown(minHeap, k, j); } // 继续读取后N-K int val = 0; while (fscanf(fout, "%d", &val) != EOF) { if (val > minHeap[0]) { minHeap[0] = val; AdjusuDown(minHeap, k, 0); } } for (int i = 0; i < k; ++i) { printf("%d ", minHeap[i]); } free(minHeap); fclose(fout); } int main() { const char* filename = "Data.txt"; int N = 10000; int K = 10; //CreateDataFile(filename, N); PrintTopK(filename, K); return 0; }void CreateDataFile(const char* filename, int N) { FILE* fin = fopen(filename, "w"); if (fin == NULL) { perror("fopen fail"); return; } srand(time(0)); for (int i = 0; i < N; ++i) { fprintf(fin, "%dn", rand() % 1000000); } fclose(fin); } void PrintTopK(const char* filename, int k) { assert(filename); FILE* fout = fopen(filename, "r"); if (fout == NULL) { perror("fopen fail"); return; } int* minHeap = (int*)malloc(sizeof(int) * k); if (minHeap == NULL) { perror("malloc fail"); return; } // 如何读取前K个数据 for (int i = 0; i < k; ++i) { fscanf(fout, "%d", &minHeap[i]);//scanf系列会忽略中间的空格 换行 } // 建k个数小堆 for (int j = (k - 2) / 2; j >= 0; --j)//(k-1-1)/2 { AdjusuDown(minHeap, k, j); } // 继续读取后N-K int val = 0; while (fscanf(fout, "%d", &val) != EOF) { if (val > minHeap[0]) { minHeap[0] = val; AdjusuDown(minHeap, k, 0); } } for (int i = 0; i < k; ++i) { printf("%d ", minHeap[i]); } free(minHeap); fclose(fout); } int main() { const char* filename = "Data.txt"; int N = 10000; int K = 10; CreateDataFile(filename, N);// PrintTopK(filename, K); return 0; }