基于堆与AdjustDown的TOP-K问题

TIPS

TOP-K问题

1. TOP-K问题：就是说现在比如说有n个数据，然后需要从这n个数据里面找到最大的或最小的前k个。

2. 一般来讲思路的话就是：先把这n个数据给他建一个堆，建堆完成之后，然后就去调堆，然后大概只需要调k次，然后就可以把前k个数据给他找到。

3. 但比如说这个N它有时候会很大很大,比如说100亿，那这样的话100亿整数大概需要占40gb的内存。如果说还是按上面这个方法去做的话，光去建一个堆就要去申请40gb的内存，不可能啊。1G大约10亿字节

4. 比如说现在n是100亿，也就是说有100亿个整数，然后比如说需要找到前50大的整数，该怎么办？

5. 对于这种topk问题的话，实际上有个贼简单的方法。他现在题目中不是说有100亿个整数，然后需要去找到前50大的整数。我就直接利用他100亿个数据当中前50个数据先去建一个堆，而且是小根堆。然后去遍历剩下的所有数据，如果说那个数据比我这个堆顶的数据要大，就代替它进堆并向下调整Adjustadown。

6. 这个方法他真正厉害的地方就在于他是一个小根堆。因为如果这样子的话，最大的前k个数一定能够进堆，就是说不存在，比如说有一个特别特别大的树放在堆顶，然后阻挡最大的前k个数进入。因为首先我这个堆里面的数据总共也就是k一个，其次就是这是一个小根堆，比较大的树它都是在堆底，就意味着在堆顶上面的数据是最小的。

7. 如果说我要从非常非常非常多的数据当中找到前k个最小的数据，那我这时候就要建一个大根堆（有k个节点）。如果说我要求非常非常非常多的数据当中找到前k个最大的数据，那我这时候就要建一个小根堆（有k个节点）。

8. 然后接下来依次去遍历所有的那些非常多的数据，然后与堆顶的元素进行比较，比如说我要求前k个最小的，我现在已经建了一个大根堆，如果说我遍历的元素比堆顶的元素要来的小，那就先去取代堆顶，然后接下来AdjustDown；如说我要求前k个最大的，我现在已经建了一个小根堆，如果说我遍历的元素比堆顶的元素要来的大，那就先去取代堆顶，然后接下来AdjustDown。这个与之前的堆排序有点差不多，都是有点逆直觉：比如说在堆排序当中，如果我要升序排列，就要建大根堆；如果说我要降序排列，就要减小根堆

9. 然后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 (child+1<n && 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问题他主要就是利用在堆当中所有的元素中堆顶是最值，因此每次就要去堆顶比较，并不断试图去代替他，一旦把他代替了之后，堆被破坏了，这时候还要复原回堆，然后再去利用堆着那个特别厉害的性质（堆顶元素是所有元素当中的最值）