557-大数据处理-求topK问题

秒速五厘米 2022-09-11 08:24 205阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

## 大/小根堆求topK问题 ##

**问题1：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
如果我们用普通排序算法，时间复杂度是O(n^2)，如果我们使用高级排序算法，时间复杂度是O(logn)。  
**但是现在要求时间复杂度是O(n）**  
![在这里插入图片描述][4c4073b986ec4f93830abf70844ebe29.png]  
**相当于把原始数据遍历一遍就找到topK元素。**  
我们需要一个大根堆（堆顶元素的值是最大的）（二叉堆访问的就是堆顶，其他位置我们访问不到，和栈一样，我们只能访问栈顶，其他位置访问不到）  
![在这里插入图片描述][47706eca8db642a2959bd0d1458cf21e.png]  
我们先遍历序列的前3(k)个元素，先把它们构建成1个大根堆，堆顶元素就是64，  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

然后前面这3个元素已经遍历过了，然后从第4个元素开始继续遍历，因为我们要留下小的元素，**80大于堆顶元素64，就是比这个堆的所有元素都大**，就不管了，就继续遍历，66大于64，也不管了，继续遍历，68大于64，也不管了，继续遍历，0小于堆顶元素64，然后把堆顶元素64出堆，出堆之后就要调整，52就成堆顶了，0入堆![在这里插入图片描述][1b3a71e3ecc9477f96ecb4ea990bfc1d.png]  
2小于堆顶元素52，把堆顶元素52出堆，2入堆  
![在这里插入图片描述][ed0dc14dc32e40c28ef6cf9246ace8e4.png]  
18小于堆顶元素45，45出堆，18入堆  
![在这里插入图片描述][1c511084993b4b72889a50114c8aaf26.png]  
**75大于堆顶元素18，就不管了，遍历结束。**  
**这一系列过程就是花费O(n)的时间复杂度。**  
![在这里插入图片描述][ae2722bf938c47f19bbdac23dd2bc0a3.png]  
大根堆的调整也要花费时间，O(logk）  
总的时间复杂度：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**但是这个k是常数，就去掉了。  
就是O(n)**

**问题2：**  
![在这里插入图片描述][7a3378823d154259b8655e2d661c53da.png]

**小根堆，堆顶元素是堆中值最小的元素**  
我们先把前3个元素构建小根堆  
![在这里插入图片描述][8294a81a85fc4d92a16b84a39aed9175.png]  
80大于堆顶元素45，把45出堆，80入堆  
![在这里插入图片描述][8ec00420d3b9418989cff39c58275fe5.png]  
66大于堆顶元素52，52出堆，66入堆  
![在这里插入图片描述][482b83e32ba94d518e18a02b964eeb76.png]  
68大于堆顶元素64,64出堆，68入堆  
![在这里插入图片描述][37c9cc8634a8413d819cd34ba824f71a.png]  
0,2，18都比堆顶元素66小，就不管了  
75大于堆顶元素，66出堆，75入堆  
![在这里插入图片描述][208c3c8f393145a5a99cf255a995d041.png]

## 大/小根堆求topK问题代码实现 ##

int main()
    {
        
        vector<int> vec;
        srand(time(NULL));
        for (int i = 0; i < 1000; i++)
        {
        
            vec.push_back(rand() % 10000);
        }
    
    
        //求vec中值最小的前5个元素
        priority_queue<int> maxheap;//默认是大根堆 
        int k = 5;
    
        //由前k个元素构建一个大根堆
        for (int i = 0; i < 5; i++)
        {
        
            maxheap.push(vec[i]);
        }
    
        //遍历剩余的元素直到最后
        for (int i = 5; i < vec.size(); i++)
        {
        
            if (maxheap.top() > vec[i])
            {
        
                maxheap.pop();
                maxheap.push(vec[i]);
            }
        }
    
        //输出结果
        while (!maxheap.empty())
        {
        
            cout << maxheap.top() << " ";
            maxheap.pop();
        }
        cout << endl;
    	return 0;
    }

int main()
    {
        
        vector<int> vec;
        srand(time(NULL));
        for (int i = 0; i < 1000; i++)
        {
        
            vec.push_back(rand() % 10000);
        }
    
    
        //求vec中值最大的前5个元素
        priority_queue<int, vector<int>, greater<int>> minheap;//小根堆
        int k = 5;
    
        //由前k个元素构建一个大根堆
        for (int i = 0; i < 5; i++)
        {
        
            minheap.push(vec[i]);
        }
    
        //遍历剩余的元素直到最后
        for (int i = 5; i < vec.size(); i++)
        {
        
            if (minheap.top() < vec[i])
            {
        
                minheap.pop();
                minheap.push(vec[i]);
            }
        }
    
        //输出结果
        while (!minheap.empty())
        {
        
            cout << minheap.top() << " ";
            minheap.pop();
        }
        cout << endl;
    
        /*for (auto key : vec)
        {
            cout << key << " ";
        }
        cout << endl;*/
        
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]

#include <iostream>
    #include <vector>
    #include <stdlib.h>
    #include <time.h>
    #include <queue>
    #include <functional>//函数对象 
    #include <unordered_map>
    using namespace std;
    
    //查重和top k问题综合起来了
    int main()
    {
        
        vector<int> vec;
        srand(time(NULL));
        for (int i = 0; i < 10000; i++)
        {
        
            vec.push_back(rand() % 1000);
        }
    
        //统计重复次数最小的前3个数字
        int k = 3;
        unordered_map<int, int> map;//底层是哈希表 
        for (auto key : vec)
        {
        
            map[key]++;
        }
    
        //放入大根堆的时候，需要放key-value键值对
        using Type = pair<int, int>;
        using Comp = function<bool(Type&, Type&)>;
        priority_queue<Type, vector<Type>, Comp> maxheap(
            [](Type& a, Type& b)->bool {
        
                return a.second < b.second;
            });
    
        auto it = map.begin();
        for (int i = 0; i < k; i++, ++it)
        {
        
            maxheap.push(*it);
        }
    
        for (; it != map.end(); ++it)
        {
        
            if (maxheap.top().second > it->second)
            {
        
                maxheap.pop();
                maxheap.push(*it);
            }
        }
    
        while (!maxheap.empty())
        {
        
            cout << "key:" << maxheap.top().first
                << " cnt:" << maxheap.top().second << endl;
            maxheap.pop();
        }
    
    
        //统计重复次数最大的前3个数字
        int k = 3;
        unordered_map<int, int> map;
        for (auto key : vec)
        {
        
            map[key]++;
        }
    
        //放入大根堆的时候，需要放key-value键值对
        using Type = pair<int, int>;
        using Comp = function<bool(Type&, Type&)>;
        priority_queue<Type, vector<Type>, Comp> minheap(
            [](Type& a, Type& b)->bool {
        
                return a.second > b.second;
            });
    
        auto it = map.begin();
        for (int i = 0; i < k; i++, ++it)
        {
        
            minheap.push(*it);
        }
    
        for (; it != map.end(); ++it)
        {
        
            if (minheap.top().second < it->second)
            {
        
                minheap.pop();
                minheap.push(*it);
            }
        }
    
        while (!minheap.empty())
        {
        
            cout << "key:" << minheap.top().first
                << " cnt:" << minheap.top().second << endl;
            minheap.pop();
        }
    }

## 快排分割算法求topK问题 ##

![在这里插入图片描述][54202fadc08b44d18aca4a932982ff55.png]  
**找值最小的前3个元素**  
我们没有必要把全部数据排序。  
我们选择一个基准数：64  
然后头尾定义i,j  
![在这里插入图片描述][fc3d0af5f30c4bb58668bb9998f6fdaf.png]

从右向左找小于基准数64的，75大于64，18小于64，把18放在左边i的位置上，i++，然后从左向右找，大于基准数的。

![在这里插入图片描述][39889ef16d9844bc884ab4d7268c95ec.png]  
找到80大于基准数64，把80放到右边j的位置，j–  
![在这里插入图片描述][2eb7be554e8043cf92c19b9fdbef265c.png]

从右向左找小于基准数64的，2小于基准数，把2给i的位置，i++  
![在这里插入图片描述][6d4c80fc87f64d018e4abd075a358ba8.png]  
然后从左向右找，大于基准数的。66大于基准数64，66放到j的位置，j–

![在这里插入图片描述][c51dd3ae6fb647c984726c05f6929f4c.png]  
从右向左找小于基准数64的，0小于64，0放到i的位置，i++  
![在这里插入图片描述][afd4fbb94b6d41c986ab03aa23e17c49.png]  
然后从左向右找，大于基准数的，68大于64，68放到j的位置，j–  
![在这里插入图片描述][8856f9f57a84486d95461c276e865c94.png]  
i和j到同一个位置了，就结束了，把基准数64放到i和j相等的位置，然后把这个位置返回回来了。  
![在这里插入图片描述][7a4404c8a15d4efeb1cfc1139af81646.png]  
经过1次调整以后，左边的都是小于64，右边的都是大于64  
**前6个小的，就是64及它左边的元素**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
如果是要找前3小的元素，肯定不在64的右边，就继续对基准数64左边的这一列数据处理，基准数是18，**然后重复上面所述的快排方法**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
**快排结束，返回下标2  
0,2，18就是前3小的元素**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
求前3小的元素，使用了2次快排分割算法 ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
**平均时间复杂度:**  
比基准数的位置号大，就处理右边，比基准数的位置号小， 就处理左边。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]  
**如果序列是趋于有序的，那么快排的时间复杂度就差了**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]  
**对基准数的选取，采用三数取中** ’  
**如果是找前几个大的，就相反操作，比基准数大的向左边跳，比基准数小的向右边跳**

#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;
    }

![在这里插入图片描述][b6fb69993cf347f6857e2f49934f7a4c.png]  
**我们要进行三数取中的优化**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1b056788ffcd4e3c82545ab24997f34f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/883e22cf3b0248e8a33b0f995e4246f4.png
[4c4073b986ec4f93830abf70844ebe29.png]: /images/20220828/6818b4ec8d4e4ec9b31acc36bcb3c0e9.png
[47706eca8db642a2959bd0d1458cf21e.png]: /images/20220828/32e1f014ab514c9aafd0a37f6f8f270e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/474f3fc3b88a4217a0e5c1d5a783bd5f.png
[1b3a71e3ecc9477f96ecb4ea990bfc1d.png]: /images/20220828/4e52c0124bd940dea7ef377fa050322d.png
[ed0dc14dc32e40c28ef6cf9246ace8e4.png]: /images/20220828/1ad754aa9aa84642bc36f730e986dfb7.png
[1c511084993b4b72889a50114c8aaf26.png]: /images/20220828/5ee9e3abd80043d79c582dacc03e4de7.png
[ae2722bf938c47f19bbdac23dd2bc0a3.png]: /images/20220828/4b1c312eaa814075819ae358f4a26b3e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/fbbc07aba24042ecaed461839421a6e6.png
[7a3378823d154259b8655e2d661c53da.png]: /images/20220828/909732e99cbd4da69d6343398a3edcd6.png
[8294a81a85fc4d92a16b84a39aed9175.png]: /images/20220828/051815f97ccb48cf81f5715af59e97dc.png
[8ec00420d3b9418989cff39c58275fe5.png]: /images/20220828/23edf2e869594a76992259e65d692462.png
[482b83e32ba94d518e18a02b964eeb76.png]: /images/20220828/3ac020aaa140449ab8a4fdcac42d3910.png
[37c9cc8634a8413d819cd34ba824f71a.png]: /images/20220828/a2331e558bb24aa9b9298e2aa75dcf94.png
[208c3c8f393145a5a99cf255a995d041.png]: /images/20220828/ea24267c17bb4814b74e4fb4fbb7ffe9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/f353d0da30f1451fb4da7bbe9c05718a.png
[54202fadc08b44d18aca4a932982ff55.png]: /images/20220828/4a4f477aae9245d7914b4c72f94c1aa9.png
[fc3d0af5f30c4bb58668bb9998f6fdaf.png]: /images/20220828/00037e0f82a34644ad29bae1442e516e.png
[39889ef16d9844bc884ab4d7268c95ec.png]: /images/20220828/403738d9726745b0ab5e43aef034f6e9.png
[2eb7be554e8043cf92c19b9fdbef265c.png]: /images/20220828/65ac4ddef90a495bb4aaee4e37a8ae59.png
[6d4c80fc87f64d018e4abd075a358ba8.png]: /images/20220828/7f1d1362af3343748abc1e0d55d7e729.png
[c51dd3ae6fb647c984726c05f6929f4c.png]: /images/20220828/1f4f443a3c5c4c089a154eebff170f69.png
[afd4fbb94b6d41c986ab03aa23e17c49.png]: /images/20220828/1ec856a5c7c64ff2a0941d2a9f5dfc0e.png
[8856f9f57a84486d95461c276e865c94.png]: /images/20220828/1fcace86750f4abeaf72eb213d2e0d27.png
[7a4404c8a15d4efeb1cfc1139af81646.png]: /images/20220828/662d6a4f000b4eb3ab58fe4ce3eb81ee.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b9710cb30972449aa9a59bd540726694.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/de3384da91d546a5b963d0a629c35190.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/b10c688f2a7b4e0a9814dbc3c944d5ed.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/6c5bbb6f8e97447185de5175da02da08.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/646879757604444fa1638f2d4601fba5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220828/3fea7148f28c44949a0642fff1d5b349.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/94a27fa700c6428b92798fce127eabc5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c149bde657b54d748b25ccea2c21378c.png
[b6fb69993cf347f6857e2f49934f7a4c.png]: /images/20220828/784264c255384c029278fc2d355b8f2d.png