C语言堆结构处理TopK问题详解
问题
在一百万个数据中，求出最大的k个数字，怎么效率高。
1. 将一百万个数据排序，承接上一篇的堆排序，时间复杂度为O(N * LogN)。但是显然这并不是最优解。
2. 一百万个数据放入一个数组中，将其视为一个完全二叉树，并用向下调整算法将其调整为一个大堆/小堆，然后Top/Popk次，即可求出前K个最大/最小的数字，时间复杂度为：O（N + K*LogN）
3. 用正确的堆处理TopK算法： 先假设求最大的K个数字，则建立大小为K的小根堆，然后在一百万-k个数据中，逐个遍历，若某个数据比小根堆的堆顶元素大，则替换掉堆顶元素，然后向下调整，使得这个堆重新变回一个小根堆。 时间复杂度为:O(K + (N-k)*LogK)
其实相较于2，3并没有时间上的很大提升，但是3在空间复杂度上有了巨大提升，2的空间为O(N),3为O(K)。 折中思考，3方法是求数据量较大的数据集合中前K个最大值/最小值的最佳方法
分析
求K个最大值，建小堆，是因为，若遍历途中遇到了那K个数中的某一个，他一定比堆顶元素大，然后替换进去之后，向下调整，可以使得这个数字置于这个小根堆的底部。从而达到目的。
代码实现
void AdjustUp(int* a, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
swap(a[parent], a[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void AdjustDown(int* a,int size, int parent) // size 是总大小，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 Print_Heap_Topk(int* a, int n, int k)
{
int* KMaxHeap = new int[k]; // 最大堆存最小的K个数
for (int i = 0; i < k; ++i)
{
KMaxHeap[i] = a[i];
}
for (int i = (k - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(KMaxHeap, k, i);
}
for (int i = k; i < n; ++i)
{
if (a[i] < KMaxHeap[0])
KMaxHeap[0] = a[i];
AdjustDown(KMaxHeap, k, 0);
}
for (int i = 0; i < k; ++i)
{
cout << KMaxHeap[i] << " ";
}
cout << endl;
}
void test_topk()
{
int n = 10000;
int* a = new int[n];
srand(time(0));
for (int i = 0; i < n; ++i)
a[i] = rand() % 1000000;
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[120] = 1000000 + 5;
a[99] = 1000000 + 6;
a[0] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[3144] = 1000000 + 10;
a[333] = -100;
a[999] = -200;
a[777] = -500;
a[888] = -800;
a[111] = -1000;
a[798] = -1;
a[1111] = -250;
a[2222] = -350;
a[3333] = -450;
a[4444] = -550;
Print_Heap_Topk(a, n, 10);
}
int main()
{
test_topk();
return 0;
}到此这篇关于C语言堆结构处理TopK问题详解的文章就介绍到这了,更多相关C语言TopK问题内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！
相关文章