堆排序和TopK问题
程序员文章站
2024-03-15 21:48:12
...
堆是一种很有趣的数据结构,有最大堆和最小堆两种形式,在上一篇文章里已经讲到了最大最小堆的建立;
这里用一下堆的方法解决问题。
1.首先是在一大堆数字中找到K个最大或最小的数字(topK问题)
topK问题是生活中很常见的问题;比如找到N个在某个科目成绩最好的同学,或者在很多游戏中都会有很多数据分析结果,年度评价之列的都是什么游戏时间最长啦,与你开黑时间最多的K个小伙伴啦,都会用到。
若是用普通的方式遍历所有元素,让元素个数很大,几亿或者几十亿,每次遍历出一个数都要比较K个数,则时间复杂度为N*K,K个数有序的话这个复杂度会少,但是排一个序也需要很多时间复杂度。所以这里可以利用堆最大K个数我们可以用这K个数组成一个最小堆(最小堆算的上是一个不完整的排序),堆顶则是这K个数中最小的数,新来的数只要比这K个数中最小的大即可入堆;再次调整堆,消耗的时间复杂度也不高(lg K)。所以使用堆求TopK 时间复杂度只有 O(K*lgK)。
下面看一下代码↓
void TopK(int* arr, size_t k, size_t n)
{
Heap<int,Less<int>> _a(arr, k); //建立最小堆
for (int i = k; i < n; i++)
{
if (_a.Top()< arr[i]) //比堆顶大进入堆
{
_a.Push(arr[i]);
_a.Pop(); //原堆顶数据出堆 会自动将刚最后入堆的数据放到堆顶
}
}
_a.Printf();
}
看一下测试:
void TestTopK()
{
srand((int)time(NULL));
int a[100] = { 0 };
for (int i = 0; i < 100; i++)
{
a[i] = rand() % 200;
}
a[20] += 200; //使其中10个数大于200 结果就是这大于200的10个数
a[30] += 200;
a[40] += 200;
a[50] += 200;
a[60] += 200;
a[70] += 200;
a[80] += 200;
a[90] += 200;
a[10] += 200;
a[0] += 200;
TopK(a, 10, 100);
}
求出了这K个数;
2.堆选择排序
简单选择排序的时间复杂度为O(n^2),每次遍历并选择最小或最大的一个数其实消耗了很多时间,利用堆来选择可以节约一些时间,最大最小堆的堆顶即为最大或最小的数,这对于选择便不用再遍历了,只需每次调整堆,调整堆的时间复杂堆只有lgN。
先建堆(比如需要升序就建最大堆),每次将堆顶a[0]数与a[n-1],再使n--;调整新堆。
void MaxHeap(int * a,int root,int n)
{
int parent = root;
int child = parent * 2 + 1;
while (child < n)
{
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; //循环到孩子小于父亲便可停止
}
}
void CreatHeap(int *a, int n) //大堆
{ int root = (n - 2) / 2;
for (; root >= 0; root--)
{
MaxHeap(a, root, n);
}
}
void HeapSort(int *a,int n)
{
CreatHeap(a, n); //先最大建堆
for (; n > 0; n--)
{
swap(a[0], a[n - 1]);
MaxHeap(a, 0, n-1); //调整新堆O(lgN)
}
}
void TestHeapSort()
{
srand((int)time(NULL));
int a[50] = { 0 };
for (int i = 0; i < 50; i++)
{
a[i] = rand() % 100;
}
HeapSort(a, 50); //堆排序
for (int i = 0; i < 50; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
int main()
{
TestHeapSort();
system("pause");
return 0;
}
排序完成
推荐阅读
-
堆排序和TopK问题
-
使用最小堆解决海量数据数据中求TopK最大的几个数问题
-
查找 TopK 问题
-
求阶乘以及求各项阶乘和问题
-
RSA加密例子和中途遇到的问题 算法 RSA
-
Eclipse将第三方jar包插件和项目一起发布到web容器中 博客分类: eclipse eclipseweblogic.servlet.jsp.CompilationExceptionjsp编译问题
-
Eclipse将第三方jar包插件和项目一起发布到web容器中 博客分类: eclipse eclipseweblogic.servlet.jsp.CompilationExceptionjsp编译问题
-
用深度学习(CNN RNN Attention)解决大规模文本分类问题 - 综述和实践
-
空格和换行符造成3像素距离问题解决
-
最大公约数和最小公倍数问题