priority_queue用法笔记与Top K Frequent Elements结合

小咪咪 2022-05-25 04:42 122阅读 0赞

### 简介 ###

priority\_queue是有权值的队列。默认使用大根堆来实现。  
push() 从队尾插入，经过堆调整至合适的位置。  
top() 查看队头数据。  
pop() 弹出队头数据。

// priority_queue.cpp: 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include <iostream>
    #include <queue>
    #include <functional>
    using namespace std;
    void testInt()
    {
        //priority_queue<int> q;默认大根堆从大到小排序
        priority_queue<int, vector<int>, greater<int>> q;//修改成小根堆，所以从小到大输出。
        q.push(5);
        q.push(6);
        q.push(3);
        q.push(7);
        q.push(1);
        while (!q.empty())
            cout << q.top() << endl, q.pop();
    }
    class Node
    {
    public:
        Node(int x,int y):m_x(x), m_y(y){}
    public:
        int m_x;
        int m_y;
    };
    void testNode()
    {
        auto cmp = [](const Node& a, const Node& b) {
       return a.m_x > b.m_x; };
        vector<Node> vn{ Node(1, 2), Node(2, 3), Node(0, 4), Node(-1, 5) };
        priority_queue<Node, vector<Node>, decltype(cmp)> q(vn.begin(), vn.end(), cmp);
        while (!q.empty())
            cout << q.top().m_x << ' ' << q.top().m_y << endl, q.pop();
    }
    int main()
    {
        testInt();
        testNode();
        cin.get();
        return 0;
    }

ps：注意点  
1. priority\_queue的构造可以一个一个push，也可以直接从一个vector构造。  
2. 在需要自定义比较函数的时候，必须用`priority_queue<Type, vector<Type>, function>`  
3. 比较函数可以用传统的函数对象，也可以用c++11中lambda表达式。

struct cmp
    {
        bool operator()(const Node& a, const Node& b)
        {
            return a.m_x > b.m_x;
        }
    }

### 例子 ###

这里在给一个leetcode的例子。347. Top K Frequent Elements  
简单来说就是统计词频，输出前K个频率最高的数。

class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> um;
            priority_queue<pair<int, int>> pq;
            vector<int> ret;
            for(auto x : nums) ++um[x];
            for(auto it : um) pq.push({it.second, it.first});
            for(auto i = 0; i != k; ++i)
                ret.emplace_back(pq.top().second),pq.pop();
            return ret;
        }
    };

利用hasttable获取词频，priority\_queue取前k个值。  
这里需要注意点就是 对于pair<>类型的默认比较用的first，所以才有了`pq.push({it.second, it.first});`  
要是不了解的，不清楚，还是自己定义比较函数比较好。

class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> um;
            auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
       return a.second < b.second;};
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
            vector<int> ret;
            for(auto x : nums) ++um[x];
            for(auto it : um) pq.push(it);
            for(auto i = 0; i != k; ++i)
                ret.emplace_back(pq.top().first),pq.pop();
            return ret;
        }
    };

PS：c++11for语言 x， it都是对应容器的类型对象。  
\++um\[x\],当x不在hastmap中，会默认构造一个int = 0的对象。

再提供一个桶排的实现。

class Solution {
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> um;
            vector<vector<int>> bucket(nums.size() + 1);
            vector<int> ret;
            for(auto x : nums) ++um[x];
            for(auto it : um) bucket[it.second].emplace_back(it.first);
            for(auto i = bucket.size() - 1; i >= 0; --i)
            {
                for(auto j = 0; j != bucket[i].size(); j++)
                {
                    ret.emplace_back(bucket[i][j]);
                    if(ret.size() == k)
                        return ret;
                }
            }
            return ret;
        }
    };

用二维的原因是可能有词频相同的。和hash冲突类似。