住房住房和城乡建设厅网站,申请摇号广州网站,今天31个省新增最新消息,建设银行信用卡积分兑换话费网站TIPSTOP-K问题TOP-K问题#xff1a;就是说现在比如说有n个数据#xff0c;然后需要从这n个数据里面找到最大的或最小的前k个。一般来讲思路的话就是#xff1a;先把这n个数据给他建一个堆#xff0c;建堆完成之后#xff0c;然后就去调堆#xff0c;然后大概只需要调k次就是说现在比如说有n个数据然后需要从这n个数据里面找到最大的或最小的前k个。一般来讲思路的话就是先把这n个数据给他建一个堆建堆完成之后然后就去调堆然后大概只需要调k次然后就可以把前k个数据给他找到。但比如说这个N它有时候会很大很大,比如说100亿那这样的话100亿整数大概需要占40gb的内存。如果说还是按上面这个方法去做的话光去建一个堆就要去申请40gb的内存不可能啊。1G大约10亿字节比如说现在n是100亿也就是说有100亿个整数然后比如说需要找到前50大的整数该怎么办对于这种topk问题的话实际上有个贼简单的方法。他现在题目中不是说有100亿个整数然后需要去找到前50大的整数。我就直接利用他100亿个数据当中前50个数据先去建一个堆而且是小根堆。然后去遍历剩下的所有数据如果说那个数据比我这个堆顶的数据要大就代替它进堆并向下调整Adjustadown。这个方法他真正厉害的地方就在于他是一个小根堆。因为如果这样子的话最大的前k个数一定能够进堆就是说不存在比如说有一个特别特别大的树放在堆顶然后阻挡最大的前k个数进入。因为首先我这个堆里面的数据总共也就是k一个其次就是这是一个小根堆比较大的树它都是在堆底就意味着在堆顶上面的数据是最小的。如果说我要从非常非常非常多的数据当中找到前k个最小的数据那我这时候就要建一个大根堆有k个节点。如果说我要求非常非常非常多的数据当中找到前k个最大的数据那我这时候就要建一个小根堆有k个节点。然后接下来依次去遍历所有的那些非常多的数据然后与堆顶的元素进行比较比如说我要求前k个最小的我现在已经建了一个大根堆如果说我遍历的元素比堆顶的元素要来的小那就先去取代堆顶然后接下来AdjustDown如说我要求前k个最大的我现在已经建了一个小根堆如果说我遍历的元素比堆顶的元素要来的大那就先去取代堆顶然后接下来AdjustDown。这个与之前的堆排序有点差不多都是有点逆直觉比如说在堆排序当中如果我要升序排列就要建大根堆如果说我要降序排列就要减小根堆然后popk问题不要与堆排序问题扯到一起因为这个的话只涉及到建堆AdjustDown并没有涉及到调堆。但如果说有额外要求的话说在很多很多数据当中求出前k个最小的数据并且对于这k个数据也要进行排序的话那么这时候就要额外加上堆排序的调堆TOP-K问题的演示解决这个先必须得有void Swap(int* p1, int* p2)
{assert(p1 p2);int tmp *p1;*p1 *p2;*p2 tmp;
}
void AdjustDown(int* a, int parent, int n)
{assert(a);int child 2 * parent 1;while (child n){if (child1n a[child] a[child 1]){child;}if (a[parent] a[child]){Swap(a parent, a child);parent child;child 2 * parent 1;}else{break;}}
}造数据#define ALL_NUMBER 10000000
#define SELECT_NUMBER 10
void CreateNumber()
{srand((unsigned int)time(NULL));FILE* pf fopen(test.txt, w);assert(pf);for (int i 0; i ALL_NUMBER; i){fprintf(pf, %d, rand() * 12345 % 1000000);}fclose(pf);pf NULL;
}TOP-K过程void PrintPopK()
{FILE* pf fopen(text.txt, r);assert(pf);//建堆int arr[SELECT_NUMBER] { 0 };for (int i 0; i SELECT_NUMBER; i){fscanf(pf, %d, arr[i]);}for (int i (SELECT_NUMBER - 1 - 1) / 2; i 0; i--){AdjustDown(arr, i, SELECT_NUMBER);}//遍历所有数据看能否入堆int val;int ret;while ((ret fscanf(pf, %d, val)) ! EOF){if (val arr[0]){arr[0] val;AdjustDown(arr, 0, SELECT_NUMBER);}}//此刻前k小的数已经在堆里面了我还想排序一下int end SELECT_NUMBER - 1;while (end 0){Swap(arr 0, arr end);AdjustDown(arr, 0, end);end--;}//最终打印结果for (int i 0; i SELECT_NUMBER; i){printf(%d , arr[i]);}fclose(pf);pf NULL;
}总代码#define ALL_NUMBER 1000000
#define SELECT_NUMBER 10
void CreateNumber()
{FILE* pf fopen(text.txt, w);assert(pf);for (int i 0; i ALL_NUMBER; i){fprintf(pf, %d\n, rand() * (rand()%10000) % 1000000);}fclose(pf);pf NULL;
}void PrintPopK()
{FILE* pf fopen(text.txt, r);assert(pf);//建堆int arr[SELECT_NUMBER] { 0 };for (int i 0; i SELECT_NUMBER; i){fscanf(pf, %d, arr[i]);}for (int i (SELECT_NUMBER - 1 - 1) / 2; i 0; i--){AdjustDown(arr, i, SELECT_NUMBER);}//遍历所有数据看能否入堆int val;int ret;while ((ret fscanf(pf, %d, val)) ! EOF){if (val arr[0]){arr[0] val;AdjustDown(arr, 0, SELECT_NUMBER);}}//此刻前k小的数已经在堆里面了我还想排序一下int end SELECT_NUMBER - 1;while (end 0){Swap(arr 0, arr end);AdjustDown(arr, 0, end);end--;}//最终打印结果for (int i 0; i SELECT_NUMBER; i){printf(%d , arr[i]);}fclose(pf);pf NULL;
}int main()
{srand((unsigned int)time(NULL));CreateNumber();PrintPopK();return 0;
}
体悟TOP-K问题他主要就是利用在堆当中所有的元素中堆顶是最值因此每次就要去堆顶比较并不断试图去代替他一旦把他代替了之后堆被破坏了这时候还要复原回堆然后再去利用堆着那个特别厉害的性质堆顶元素是所有元素当中的最值
