大数据TopK问题

TopK问题

能够在O(n)线性时间复杂度找到海量数据的前k个元素(top k)，可以采用大小根堆算法、快排分割算法解决。应用：TOP10热词推荐、TOP店铺推荐、外卖评分最低的10家等等。

大小根堆算法

举例说明大小根堆算法解决TopK问题思想：给出一个随机序列

1、求出序列中值最小前3个元素（大根堆）
2、求出序列中值最大前3个元素（小根堆）

大根堆

1、求出序列中值最小前3个元素（大根堆）
大根堆堆顶元素的值是最大的，思想：利用k个元素构建大根堆，把大根堆的堆顶最大值不断淘汰，放入最小值。

小根堆

2、求出序列中值最大前3个元素（小根堆）
小根堆堆顶元素的值是最小的，思想：利用k个元素构建小根堆，把小根堆的堆顶最小值不断淘汰，放入最大值。

堆内调整的时间复杂度为常数级。 所以能在线性时间内完成。

代码实现

1、随机实现序列，求其中的low5、top5。

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h> 
#include<queue>
#include<functional>
using namespace std;

int main(){
	vector<int> vec;
	srand(time(NULL));
	for(int i = 0 ; i < 100 ; ++i){
		vec.push_back(rand() % 10000);
	}
	
	//求vec中值最小的前五个元素  定义一个优先队列 
	priority_queue<int> low5;
	int k = 5; 
	//前k个元素构建一个大根堆 
	for(int i = 0 ; i < k ; ++i){
		low5.push(vec[i]);
	}
	//剩下的元素遍历
	for(int i = k ; i < vec.size() ; ++i){
		//当前元素小于堆顶元素时 调整 
		if(low5.top() > vec[i]){		
			low5.pop();
			low5.push(vec[i]);
		}
	} 
	//输出low5
	while(!low5.empty()){
		cout<< low5.top() << " ";
		low5.pop();
	}
	cout<<endl;
	
	//求vec中值最大的前五个元素 定义一个从小到大排序的优先队列
	priority_queue<int, vector<int>, greater<int>> top5;
	//前k个元素构建一个小根堆 
	for(int i = 0 ; i < k ; ++i){
		top5.push(vec[i]);
	}
	//剩下的元素遍历
	for(int i = k ; i < vec.size() ; ++i){
		//当前元素大于堆顶元素时 调整 
		if(top5.top() < vec[i]){		
			top5.pop();
			top5.push(vec[i]);
		}
	} 
	//输出low5
	while(!top5.empty()){
		cout<< top5.top() << " ";
		top5.pop();
	}
	cout<<endl;
	
	
//	for(auto val : vec){
//		cout<< val <<" ";
//	}
//	cout<<endl;
	
	
	return 0;
} 

2、查重问题结合topK综合：统计重复次数最小的前三个元素。

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h> 
#include<queue>
#include<functional>
#include<unordered_map>
using namespace std;

int main(){
	vector<int> vec;
	srand(time(NULL));
	for(int i = 0 ; i < 10000 ; ++i){
		vec.push_back(rand() % 100);
	}
	
	//统计重复次数 求出现次数最小的前三个数字
	 unordered_map<int ,int> map;
	 int k = 3;
	 for(auto val : vec){
	 	map[val]++;
	 } 
	 //大根堆中放入key-value  自定义排序 
	 using _type = pair<int,int>;
	 // 大根堆比较函数
	 auto cmp = [](const _type& a, const _type& b) { 
        return a.second < b.second; 
    };
//	 using Comp = functional<bool(_type&, _type&)>; 
	 priority_queue<_type, vector<_type> , decltype(cmp)> low3(cmp);
	  
	auto it = map.begin();
	for(int i = 0 ; i < k ; ++i, ++it){
		low3.push(*it);
		
	} 
	for(; it != map.end() ; ++it){
		if(low3.top().second > it->second){
			low3.pop();
			low3.push(*it);
		}
	}
	while(!low3.empty()){
		cout<<"key:" << low3.top().first
		<<"ans"<<low3.top().second<<endl;
		low3.pop();
	}
	
	return 0;
} 

快排分割算法

举例说明快排分割算法解决TopK问题思想：给出一个随机序列求前三最小值；

代码实现

#include <iostream>
using namespace std;
//快排分割函数
int Partation(int arr[], int begin, int end)
{
    int val = arr[begin];
    int i = begin;
    int j = end;
 
    while (i < j)
    {
        while(i < j && arr[j] > val)
            j--;
 
        if (i < j)
        {
            arr[i] = arr[j];
            i++;
        }
 
        while (i < j && arr[i] < val)
            i++;
 
        if (i < j)
        {
            arr[j] = arr[i];
            j--;
        }
    }
 
    arr[i] = val;
    return i;
}
//求top k的函数
void SelectTopK(int arr[], int begin, int end, int k)
{
    int pos = Partation(arr, begin, end);
    if (pos == k - 1)
    {
        return;
    }
    else if (pos > k - 1)
    {
        SelectTopK(arr, begin, pos - 1, k);
    }
    else
    {
        SelectTopK(arr, pos + 1, end, k);
    }
}
int main()
{
    int arr[] = { 64, 45, 52, 80, 66, 68, 0, 2, 18, 75 };
    int size = sizeof arr / sizeof arr[0];
 
    //求值最小的前3个元素
    int k = 3;
    SelectTopK(arr, 0, size - 1, k);
 
    for (int i = 0; i < k; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}