赞
踩
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
这个方法很容易想到,用我们的堆排序解决的话,时间复杂度是O(nlogn).
void Swap(HPDataType* p1, HPDataType* p2) { HPDataType tmp; tmp = *p1; *p1 = *p2; *p2 = tmp; } //向下调整 void ADjustDown(HPDataType* data, HPDataType father,int size) { //法一:迭代 //HPDataType child = father * 2 + 1; // //if ((data[child] < data[child + 1])&&(child+1<size))//找到孩子较大的一个 //if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个 //{ // child++; //} //while (child<size) //{ // if (data[father] < data[child])//大堆 // //if (data[father] > data[child])//小堆 // // { // Swap(&data[father], &data[child]); // father = child;//孩子变父亲,向下迭代 // child = father * 2 + 1; // } // else // { // break; // } //} //法二:递归 HPDataType child = father * 2 + 1; if (child >= size)return; else { //if ((data[child] < data[child + 1]) && (child + 1 < size))//大堆,找到孩子较大的一个 if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个 { child++; } //if (data[father] < data[child])//大堆 if (data[father] > data[child])//小堆 { Swap(&data[father], &data[child]); } ADjustDown(data,child,size); } } void Heapsort(HPDataType* data,int size) { for (int i = (size - 1 - 1) / 2; i >= 0; i--) { ADjustDown(data,i,size); } int end = size - 1; while (end > 0) { Swap(&data[0], &data[end]); ADjustDown(data, 0, end); end--; } }
也就是说我们先建一个大堆(时间复杂度O(logn)),然后取出堆顶的元素,再删除,重复k次
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
{
ADjustDown(data,i,size);
}
for(int i=0;i<k;i++)
{
printf("%d ",HeapTop(data);
HeapPop(data);
}
因为上述两种方法都是在内存中执行的,但是当我们 n很大时,占用内存很大,比如说n为100亿,
我们知道1G=1024MB=1024 * 1024KB==1024 * 1024 * 1024Byte约等于10亿Byte左右,就算有 那么大的内存,那么成本也很高!!!
所以我们采用建一个大小为k的小堆,为什么是小堆呢,我们知道小堆是用来排升序的,当我们向后遍历数据和堆顶比较,如果比堆顶大就替换,然后在向下调整,这样就大大减小内存的使用!!
但是用人会问,哪里一开始那个数据是n个那不也很大吗??对于这个问题的解释就是数据不一定是来自内存,可能来自硬盘,数据库,网络上的,而上述两种方法都是得存在内存上的,或者我们使用归并排序,但是数据不在内存上,归并排序效率会降低!!
代码:
//向下调整 void ADjustDown(HPDataType* data, HPDataType father,int size) { //法一:迭代 //HPDataType child = father * 2 + 1; // //if ((data[child] < data[child + 1])&&(child+1<size))//找到孩子较大的一个 //if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个 //{ // child++; //} //while (child<size) //{ // if (data[father] < data[child])//大堆 // //if (data[father] > data[child])//小堆 // // { // Swap(&data[father], &data[child]); // father = child;//孩子变父亲,向下迭代 // child = father * 2 + 1; // } // else // { // break; // } //} //法二:递归 HPDataType child = father * 2 + 1; if (child >= size)return; else { //if ((data[child] < data[child + 1]) && (child + 1 < size))//大堆,找到孩子较大的一个 if ((data[child] > data[child + 1]) && (child + 1 < size))//小堆,找到孩子较小的一个 { child++; } //if (data[father] < data[child])//大堆 if (data[father] > data[child])//小堆 { Swap(&data[father], &data[child]); } ADjustDown(data,child,size); } } void PrintTopK(int* a, int n, int k) { HPDataType* kMinHeap = (HPDataType*)malloc(sizeof(HPDataType) * k); assert(kMinHeap); for (int i = 0; i < k; i++) { kMinHeap[i] = a[i]; } for (int i = (k-2)/2; i>=0; i--) { ADjustDown(kMinHeap, i,k ); } for(int j=k;j<n;j++) { if (kMinHeap[0] < a[j]) { kMinHeap[0] = a[j]; ADjustDown(kMinHeap, 0, k); } } for (int i = 0; i < k; i++) { printf("%d ", kMinHeap[i]); } } void TestTopk() { int n = 10000; int* a = (int*)malloc(sizeof(int) * n); srand(time(0)); for (size_t 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[115] = 1000000 + 5; a[2335] = 1000000 + 6; a[9999] = 1000000 + 7; a[76] = 1000000 + 8; a[423] = 1000000 + 9; a[3144] = 1000000 + 10; PrintTopK(a, n, 10); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。