DAY12：栈和队列（六）：前k个高频元素（大/小顶堆）_map 实现前k个高频

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
1
2

思路

这道题目主要涉及到如下三块内容：

1. 要统计元素出现频率
2. 对频率排序
3. 找出前K个高频元素

首先统计元素出现的频率，这一类的问题可以使用map来进行统计。key存放里面的元素，value存放元素出现的次数。

数组里的元素全部放进map里，把map里面的元素以value为基准做排序，输出排序前k的key值。

如果对所有元素进行排序，按照快速排序的时间复杂度，是O(nlogn).但是，这道题目我们本来就没有必要对所有元素进行排序，要求的是前k个高频元素，我们只需要维护k个有序的集合就可以了。只维护k个高频元素的有序集合，使用大顶堆和小顶堆数据结构即可。

大顶堆和小顶堆，非常适合在很大的数据集里，求前k个高频/低频的结果。因为较大的数据集，全部进行排序，时间复杂度会很高。大顶堆就是头部元素比孩子元素大（根节点是最大元素），小顶堆的根节点是最小元素。

为什么用优先级队列不用快速排序

因为使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列是最优的。

如何用堆求前k个高频元素

用堆去遍历一遍map里面的所有元素，堆内部就维持k个元素，map遍历结束之后，就维护了k个要求的高频元素。

小顶堆和大顶堆的选取

题目要求前 K 个高频元素，我们假设使用大顶堆，定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，就无法保留下来前K个高频元素。

而且，使用大顶堆就要把所有元素都进行排序，大顶堆不能只排序k个元素，只能一次性全部排完。

示例：维护一个k大小的大顶堆，堆pop元素的时候，是弹出堆顶的元素，也就是弹出了value最高的元素。用大顶堆遍历map结束之后，堆里面剩下的应该是K个value最小的。

因此，要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

堆以value为基准进行统计，最后输出key值。

用堆的时间复杂度

如果是对map里的所有元素排序，时间复杂度为O(nlogn)。如果用小顶堆来遍历数组，遍历一遍是n，在堆里面每加入一个元素，时间复杂度是log(k)。**在数组n很大，k相对来说比较小的情况下，用堆来排序有明显的优势。**本题也是用堆来解决的很经典的类型。

（堆是二叉树结构，每加入一个元素去调整的话，时间复杂度是log(k)，因为堆的大小是k，只维护k个元素。）

堆基础部分

堆概念

堆是一棵完全二叉树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值。 每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆。STL 中的 priority_queue 其实就是一个大根堆。

所以大家经常说的大顶堆（堆头是最大元素），小顶堆（堆头是最小元素），如果懒得自己实现的话，就直接用priority_queue（优先级队列）就可以了，底层实现都是一样的，从小到大排就是小顶堆，从大到小排就是大顶堆。

（小根）堆主要支持的操作有：插入一个数、查询最小值、删除最小值、合并两个堆、减小一个元素的值。

本题我们就要使用优先级队列来对部分频率进行排序。

二叉堆的简介：二叉堆 - OI Wiki (oi-wiki.org)

cpp中大顶堆/小顶堆现成的数据结构：优先级队列

1.（容器适配器）优先级队列priority_queue

优先级队列底层实现就是堆，其实就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

优先级队列直接实现了堆这种数据结构，不用我们再自己实现堆了。

2.priority_queue在STL中的定义

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

1
2
3
4
5
6

这里，T是存储元素的类型，Container是底层容器类型，Compare是比较元素大小的函数对象。

注意：堆并不一定以pair的格式存储T，它可以存储任意类型的数据。例如，可以是int、string、自定义类等。如果存储的T是pair，那么通常是因为我们同时需要存储两种信息，如值及其频率、值及其索引等。

3.priority_queue的用法

cpp中，priority_queue是一种数据结构，特别适用于需要快速访问一组数据中的最大或最小元素的情况。priority_queue的定义中有三个模板参数：

1. T 是存储在优先队列中的元素的类型。例如：

   priority_queue<int, vector<int>, greater<int>> min_heap;
   1

   int 就是这个类型，表示 min_heap 中存储的是整数。

2. Container 是底层容器类型，用于实际存储数据。默认情况下，底层容器是 vector<T>，也就是 T 类型的动态数组。在示例代码中，vector<int> 表示底层使用的是整数向量。

3. Compare 是一个比较函数对象，用于比较优先队列中的元素。默认情况下，比较函数对象是 less<T>，使得优先队列默认实现为大顶堆（即堆顶元素是最大的元素）。但在示例代码中，比较函数对象是 greater<int>，所以 min_heap 是一个小顶堆（即堆顶元素是最小的元素）。

4.怎样区分priority_queue定义的大顶堆和小顶堆？

堆的定义取决于它的比较函数。在C++的STL库中，priority_queue默认实现的是大顶堆，也就是说堆顶元素是最大的元素。在priority_queue的定义中，第三个参数是一个比较对象，它决定了堆的性质（大顶堆或小顶堆）。

1. 大顶堆：如果比较函数定义为“小于”（<），那么创建的就是大顶堆。这是因为优先队列会将返回比较结果为false的元素放在前面，也就是说较大的元素会被放在堆顶。例如，C++的priority_queue<int>就是一个大顶堆。大顶堆的创建：

   priority_queue<int, vector<int>, less<int>> max_heap;
   1

   在这个例子中，max_heap是一个大顶堆，存储的元素类型是int，底层容器类型是vector<int>，并且使用less<int>作为比较函数对象，所以堆顶元素是最大的。

   需要注意的是，priority_queue的默认比较函数对象就是less<T>，所以如果你想创建一个大顶堆，也可以简单地写成：

   priority_queue<int> max_heap;
   1

   这行代码和上面的代码是等价的，都创建了一个大顶堆。

2. 小顶堆：如果比较函数定义为“大于”（>），那么创建的就是小顶堆。这是因为优先队列会将返回比较结果为false的元素放在前面，也就是说较小的元素会被放在堆顶。例如，要创建一个小顶堆，可以这样写：

   priority_queue<int, vector<int>, greater<int>> min_heap;
   1

   总结：如果优先队列（priority_queue）的第三个参数是greater<T>，那么就是创建了一个小顶堆。如果你想创建一个大顶堆，那么你可以使用less<T>作为第三个参数。或者直接使用默认参数。

5.priority_queue自定义比较函数

示例代码：

priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;
1

底层容器是 vector<pair<int, int>>，这意味着堆内部是用 vector 实现的，并且存储的元素类型为 pair<int, int>。

**比较函数对象是 mycomparison，它是用户自定义的比较函数对象。**这意味着堆元素的比较规则由 mycomparison 类定义的 operator() 函数决定。用户可以根据需要自定义比较函数对象，以实现特定的元素比较和排序规则。

所以，优先队列中，我们可以自定义比较函数对象。要自定义比较函数对象，通常需要定义一个类（或结构体），并在其中重载 operator() 运算符。operator() 的参数是你要比较的两个元素，返回值是一个布尔值，指示第一个元素是否应该排在第二个元素之前。

例子：

以下是自定义比较函数的一个例子。在这个例子中，我们创建一个小顶堆，但不是通过元素本身的大小来排序，而是通过元素的绝对值来排序。

#include <queue>
#include <vector>
#include <cmath>

class AbsCompare {
public:
    bool operator() (int a, int b) {
        return abs(a) > abs(b);
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, AbsCompare> pq;
    pq.push(-4);
    pq.push(2);
    pq.push(-8);
    pq.push(5);
    
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

在上述代码中，我们首先定义了一个名为 AbsCompare 的类，并在其中重载了 operator() 运算符。这个运算符接收两个 int 类型的参数 a 和 b，然后比较它们的绝对值。如果 a 的绝对值大于 b 的绝对值，那么就返回 true，表示 a 应该位于 b 之后。

然后，我们创建了一个优先队列 pq，其中元素类型为 int，底层容器类型为 vector<int>，比较函数对象为 AbsCompare。这样，pq 就是一个小顶堆，但排序规则是通过元素的绝对值来确定的。

最后，我们将几个数推入队列，然后依次取出并打印。可以看到，输出的顺序是根据数的绝对值从小到大的。

总结：

在C++中，如果要自定义一个比较函数，你需要定义一个类或结构体，并在其中重载 operator() 运算符。

6.补充

无论是大顶堆还是小顶堆，其实都取决于我们自定义的比较函数对象（也就是Compare类）。

比较函数对象决定了堆中元素的排列顺序：

• 如果你的比较函数定义为“当第一个元素<第二个元素时返回true”，那么优先队列就会形成一个大顶堆，即堆顶元素是最大的。
• 如果你的比较函数定义为“当第一个元素>第二个元素时返回true”，那么优先队列就会形成一个小顶堆，即堆顶元素是最小的。

这就意味着，优先队列中元素的排序，完全取决于你自定义的比较函数。

7.c++11新增特性：lambda表达式

// 从 C++11 开始，如果使用 lambda 函数自定义 Compare
// 则需要将其作为构造函数的参数代入，如：
auto cmp = [](const std::pair<int, int> &l, const std::pair<int, int> &r) 
{
  return l.second < r.second;
};
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >,
                    decltype(cmp)>pq(cmp);
1
2
3
4
5
6
7
8

lambda函数介绍

在这段代码中，cmp 就是一个 lambda 函数，也被称作匿名函数。lambda 函数是 C++11 引入的一种新的函数定义方式，允许在函数内定义一个局部的匿名函数。

lambda 函数的基本形式是 [] (参数列表) {函数体}：

• [] 是捕获列表，可以用来捕获外部变量供 lambda 函数使用。
• () 是参数列表，和普通函数的参数列表类似。
• {} 是函数体，包含 lambda 函数需要执行的代码。

在很多情况下，lambda 函数可以使代码更加简洁、清晰。当你需要定义一个只在当前函数中使用，且行为较为简单的函数时，可以考虑使用 lambda 函数。在 STL 中的很多算法，例如 sort、find_if 等，都可以接受一个函数作为参数来自定义行为，这些场合都可以使用 lambda 函数。

在这个例子中，由于 priority_queue 需要一个比较函数对象来确定元素的顺序，所以你可以使用 lambda 函数来定义这个比较函数对象。这样做的好处是，可以直接在 priority_queue 的定义处看到元素的比较方式，而不需要去查找比较函数对象的定义，提高了代码的可读性。

值得注意的是，由于 lambda 函数的类型是不可名的（也就是说，我们无法直接写出它的类型名），所以在作为模板参数时，需要用 decltype 关键字来获取它的类型。

使用lambda函数和compare类来自定义比较函数的优缺点

使用 lambda 函数还是自定义比较类，取决于你的具体需求和喜好。

优先考虑使用 lambda 函数的情况：

1. 如果比较逻辑简单，并且只在当前位置使用，使用 lambda 函数可以让代码更加紧凑，也能在定义处直接看到比较逻辑，提高代码的可读性。
2. 如果需要捕获外部变量，lambda 函数可以很方便地通过捕获列表来实现。

优先考虑使用自定义比较类的情况：

1. 如果比较逻辑较复杂，或者需要多处使用，那么定义一个比较类可能会更好。这样可以避免重复代码，并且可以将复杂的逻辑封装在类中，使得代码更容易维护。
2. 如果需要保存状态或者有多个比较方法，那么比较类会更适合。lambda 函数通常没有状态（除非使用可变捕获），并且每个 lambda 函数只有一个操作。

8.lambda表达式的捕获列表

在 C++ 中，Lambda 表达式的捕获列表指定了哪些外部变量可以在 Lambda 函数体中被访问，以及这些变量如何被访问（通过值或引用）。

以下是几个常见的捕获列表的例子：

• []：空捕获列表。Lambda 函数不能访问任何外部变量。

• [x]：值捕获。Lambda 函数可以访问外部变量 x，但是访问的是 x 的一个副本，而不是 x 本身。即，Lambda 函数内部对 x 的修改不会影响外部的 x。

• [&x]：引用捕获。Lambda 函数可以访问并修改外部变量 x。

• [=]：值捕获所有外部变量。Lambda 函数可以访问所有外部变量，但访问的都是副本。

• [&]：引用捕获所有外部变量。Lambda 函数可以访问并修改所有外部变量。

• [x, &y]：混合捕获。Lambda 函数可以访问外部变量 x 的副本，可以访问并修改外部变量 y。

  int x = 0;
  auto lambda = [x] () mutable { x++; std::cout << x << std::endl; }; // 输出1，但不改变外部的 x
  lambda();
  std::cout << x << std::endl; // 输出0，因为 lambda 内部修改的是 x 的副本
  
  auto lambda2 = [&x] () { x++; std::cout << x << std::endl; }; // 输出1，并改变外部的 x
  lambda2();
  std::cout << x << std::endl; // 输出1，因为 lambda2 修改了外部的 x
  1
  2
  3
  4
  5
  6
  7
  8

注意，当我们使用值捕获但又希望在 lambda 函数中修改捕获的变量时，需要在参数列表和函数体之间添加 mutable 关键字。

伪代码

//遍历数组，并用map统计频率
 unordered_map<int,int>map;
for(int i=0;i<nums.size();i++){
    //注意：要统计频率的话，key不能重复，需要单独用value来统计频率！
    //频率统计
   map(nums[i])++; //key是元素，value++、
   //value默认从0开始，直接++就行
    
   //定义小顶堆，并仅仅对value排序
    //堆内存放的是pair
    //优先级队列里面从小到大排序，就要自己实现compare函数,定义pair比较的小顶堆
   priority_queue<pair<int,int>,vector<pair<int,int>,mycomparison>que;
    for(map!it){//it就是(key,value)键值对
        //遍历一个就把键值对加入优先级队列里，对k个元素进行排序
        que.push(it);
        if(que.size()>k){
            que.pop(); //超出前k个了，就把最小的元素pop走
        }
    }
    
}
 //此时前K个高频元素已经放进队列里了
   //但是前k个高频元素，这个高频要从高到低输出
   vector<int>result;
   //倒序放入result中
  for(i=k-1;i>=0;i--){
      result[i]=que.pop().first; //小顶堆里面放的是键值对，需要用first取出key值
      que.pop(); //取值之后弹出
  }  
return result;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

• 注意技巧，当小顶堆最上面是最小元素的时候，输出数组又要求从大到小输出，可以把小顶堆元素倒着放进数组里
• 前k个高频/前k个结果的问题，可以用堆来解决

map结构的选择

因为本题目是统计key出现的频率，所以key本身不能重复；又因为没有特殊的有序/无序要求（使用堆来排序），所以使用查询和增删效率最优的unordered_map。

完整版

• 存储在优先队列里的元素类型，是pair<int,int>，所以比较函数必须重新自定义
• 注意map的遍历方式，通过迭代器iterator来实现，iterator指向map中的pair，在map中每个元素都是一个pair。
• iterator迭代器实质上是一个指针，所以push的时候需要push(*it)
• 由于小顶堆是由低到高排序，输出数组接收的时候如果要从高到底，可以让数组倒着接收，做逆序循环，注意数组逆序循环之前必须先设定好size！没有事先设置好size的话，数组会出现越界错误，因为result[k]并不存在。在 C++ 中，可以在声明vector时指定其大小。例如 vector<int> result(k); 就创建了一个大小为k的int型vector。这样安全地使用下标操作符 [] 来访问和修改 result 中的元素。
• 自定义比较函数时，比较函数类里面的函数一定要定义为public！否则默认权限为private的话，小顶堆无法访问！

class Solution {
public:
    //首先重写小顶堆的比较函数
    class compare{
    public://比较函数类里面的函数一定要定义为public！
        bool operator()(pair<int,int>& kv1,pair<int,int>& kv2){
            return kv1.second>kv2.second; //greater的写法是小顶堆
        }
    };
    //再写主函数
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //统计元素出现频率
        unordered_map<int,int>map;
        //遍历数组nums，放入map中
        for(int i=0;i<nums.size();i++){
            map[nums[i]]++;//注意map的写法！map(a)指的是key对应的value，a是key
        }
        //统计完毕出现频率后，开始建立小顶堆维护前k个高频元素
        //一定要注意这里存储在优先队列里的元素类型，是pair<int,int>！
        priority_queue<pair<int,int>,vector<pair<int,int>>,compare>pri;
        
        //固定大小为k的小顶堆，遍历map
        for(unordered_map<int,int>::iterator it=map.begin();it!=map.end();it++){
            //这一句多写几遍就会了
            pri.push(*it);//把map中的pair放到堆里,小顶堆自动进行排序
            if(pri.size()>k){
                //如果超出k了，pop出堆顶最小的那个
                pri.pop();//这里我们直接比较的是pair.second，所以直接pop就行
            }
            
        }
        
        //堆完成后，创建结果数组k，接收堆中的结果
        vector<int>result(k); //直接设置数组size
        //由于小顶堆是由低到高排序，输出接收的时候如果要从高到底，可以让数组倒着接收！
        for(int i=k-1;i>=0;i--){
            result[i]=pri.top().first; //取堆顶元素（pair）的key值
            pri.pop();
        }
        return result;
        

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

map[nums[i]]++的用法

map[nums[i]]++ 这个语句是在**对应键（key）的值（value）**进行增加。map 是一个 unordered_map<int,int> 类型的对象，存储的是数组 nums 中每个元素（作为键）和其出现次数（作为值）。

map[nums[i]] 就是获取key为 nums[i] 的value的值，这个值代表 nums[i] 的出现次数。++ 操作符则是对这个值进行自增操作，也就是增加出现次数。

当你第一次对一个哈希表中还未存在的键(key)进行操作时，C++会自动为你创建这个键(key)并初始化其值。在这种情况下，对于一个 unordered_map<int, int>，新键的值会被初始化为0。所以即使 nums[i] 在哈希表中还未出现过，map[nums[i]]++ 也可以正确地工作，也就是对于nums[i]对应的value进行自增。每次遇到一个新元素时，都可以直接对其对应的值进行自增操作，而不需要先检查这个元素是否已经在哈希表中出现过。

如果我们有一个 unordered_map（在 C++ 中通常称为哈希表或者映射），我们可以直接使用下标操作符（[]）来添加或修改键值对。如果该键不存在，C++会自动为你创建这个键并将其值初始化。对于 unordered_map<K, V>，如果 V 是基本类型，如 int，float，double等，新创建的键的值会被初始化为0。如果 V 是类类型，新创建的键的值会被默认初始化。

unordered_map<string, int> my_map;
cout << my_map["Apple"];  // 输出：0，因为 "Apple" 还没有在哈希表中，会自动创建并初始化值为0
my_map["Apple"]++;
cout << my_map["Apple"];  // 输出：1，因为 "Apple" 的值在上一行被自增了
1
2
3
4

关于pair

pair 不是只在 map 中特有的数据类型，它是 C++ 标准库中的一个基本容器类型，定义在 <utility> 头文件中。它可以用来存储一对值，这对值可以是不同类型的。

在 std::map 和 std::unordered_map 中，每个元素都是一个 pair，包含一个键和一个值。键和值可以是任何类型，如 int、float、string 等。在 pair 中，第一个元素被称为 first，它代表键，第二个元素被称为 second，它代表值。

创建一个pair：

std::pair<int, std::string> p;

p.first = 1;
p.second = "hello";

std::cout << "The pair is: " << p.first << ", " << p.second << std::endl;
1
2
3
4
5
6

本题中，每个 unordered_map 中的元素都是一个 pair，其中 pair 的 first 是 nums 数组中的元素值，pair 的 second 是该元素出现的频率。

本题必须自定义比较函数的原因

在 C++ 的 priority_queue 中，默认的比较函数是 less，其行为是创建一个大顶堆，堆顶元素最大。如果你想创建小顶堆，需要提供自定义的比较函数，如 greater。

然而，当 priority_queue 存储的是 pair 类型的元素时，这就更加复杂了。因为 pair 有两个元素：first 和 second，**默认的 less 或 greater 比较函数将会首先比较 pair 的 first 元素，如果相等，才会比较 second 元素。**这可能不符合我们的需求。

但是，本题中，我们想根据 pair 的 second 元素（即元素出现的频率）来确定优先级。因此，必须定义一个自定义的比较函数 mycomparison，在这个函数中，比较 pair 的 second 元素。这就是为什么需要自定义比较函数的原因。

priority_queue中比较函数的适应范围

std::priority_queue 的默认比较函数是 std::less，它会创建一个大顶堆。std::less 和它的对应项 std::greater 能够比较 C++ 中大部分的基础数据类型，如整型、浮点型和字符串等。

然而，**对于复杂的数据结构，如 std::pair 或自定义类型，你可能需要自定义比较函数以满足你的需求。**默认的比较函数可能并不能满足你想要的排序顺序或者优先级规则。

例如，在本题目代码中，想根据 pair 的 second 元素，也就是元素出现的频率，来创建一个小顶堆。因为默认的比较函数会首先比较 pair 的 first 元素，所以你需要定义一个自定义的比较函数 compare 来实现需求。

比较函数定义const pair的原因

在题解中，比较函数的写法是：

// 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
1
2
3
4
5
6
7

在C++中，如果你想保证函数内部不会修改参数，那么可以将参数声明为const类型。本例中，在重载的 operator() 函数中，将两个参数 lhs 和 rhs 声明为了const引用，这样就保证了在函数体内部无法修改这两个参数。

这样做有两个主要的好处：

1. 安全性： 这可以防止函数内部意外地修改参数，从而导致错误。
2. 效率： 对于大型对象，使用引用可以避免复制的开销。同时，由于使用了const，编译器可能会进行更多的优化。

所以，如果你的函数不需要修改参数，那么将参数声明为const类型是一个很好的习惯。

时间复杂度

该方法时间复杂度是O(nlogk)，空间复杂度是O(n)。

为什么时间复杂度是O(nlogk)而不是O(n+logk)?

这段代码的时间复杂度为 O(n log k) 主要是由以下几个部分构成的：

1. 创建一个哈希映射map并填充数据，这个操作的时间复杂度为 O(n) ，其中 n 是 nums 数组的长度。
2. 在哈希映射map的每个元素上进行操作，并将这些元素插入小顶堆中，这个操作的时间复杂度为 O(m log k)，这里的 m 是指哈希映射（也就是 map）中不同元素的数量。在这个问题中，哈希映射（unordered_map）用于统计 nums 数组中每个元素出现的频率。所以 m 代表 nums 中不同元素的数量。k 是堆的大小。对于堆中的插入和删除操作，它们的时间复杂度是 O(log k) 的，因为这些操作可能涉及到重新调整堆以保持其性质。
3. 从堆中取出元素并存入结果数组，这个操作的时间复杂度为 O(k log k)。

综合以上三个部分，整个算法的时间复杂度为 O(n + m log k + k log k)。在最坏的情况下，每个数字都不同，m 和 n 是相等的，所以整体时间复杂度是 O(n log k)。

这并不是 O(n+logk) ，原因是对堆的操作并不是单次操作，而是需要对 m 个元素进行堆操作，每次操作的复杂度都是 O(log k)，所以整体的复杂度就是 O(m log k)，而不是单次的 O(log k)。\

时间复杂度考虑因素补充

如果m和n相等，O(n + m log k + k log k)就会变成O(n + n log k + k log k),也就是O(n(1+logk)),也就是 O(n(1+logk) + k log k)。所以最后结果是O(nlogk)。

在大 O 表示法中，我们关注的是随着输入大小增长时，影响算法运行时间最大的那部分。**当 n 和 k 足够大的时候，n log k 项的增长率会超过 n 和 k log k，所以我们可以忽略 n 和 k log k，只保留 n log k。**所以，我们说这段代码的时间复杂度是 O(n log k)。

但是，注意，这并不意味着 n 和 k log k 的影响就完全不考虑。在实际的程序运行中，这些部分仍然会影响运行时间。但是，**当我们谈论时间复杂度时，我们主要关注的是随着输入规模的增大，哪些部分会主导总的运行时间。**在这个例子中，n log k 是主导因素，所以我们说时间复杂度是 O(n log k)。

空间复杂度

这段代码的空间复杂度主要由以下几个部分决定：

1. unordered_map：空间复杂度为 O(m)，其中 m 代表 nums 中不同元素的数量。
2. priority_queue（小顶堆）：空间复杂度为 O(k)，这是因为堆的大小最多为 k。
3. vector（结果数组）：空间复杂度为 O(k)，因为结果数组存储的是前 k 个频率最高的元素。

所以，整体的空间复杂度是 O(m + k + k) = O(m + 2k)。

但注意，在最坏的情况下，m（即nums中的不同元素数量）可能等于n（即nums的长度）。这时，空间复杂度会变为O(n + 2k)。因为 k 通常远小于 n，所以我们可以忽略掉 2k，从而认为整体的空间复杂度是 O(n)。

拓展

在写快排的cmp函数的时候，return left>right 就是从大到小，return left<right 就是从小到大。堆的比较运算在建堆时是如何应用的，为什么左大于右就会建立小顶堆，右大于左反而建立大顶堆？

（优先级队列的定义正好反过来了。估计是底层实现上优先队列队首指向后面，队尾指向最前面的缘故）

答：这个问题主要涉及到堆排序的过程，比较操作在建堆过程中的应用。

​ 在快速排序中，我们确实可以通过更改比较函数（return left>right 代表降序排序，return left<right 代表升序排序）来改变排序的方向。但在堆排序中，情况稍有不同。

​ 在建堆过程中，我们需要维护堆的性质。当我们说 "左大于右就会建立小顶堆，右大于左反而建立大顶堆"时，实际上我们是在描述父节点和子节点之间的比较操作。

假设我们有两个元素 left 和 right，其中 left 是父节点，right 是其中一个子节点：

1. 在建立小顶堆的过程中，我们需要保证父节点的值小于或等于子节点的值。如果父节点的值大于子节点的值（即 left > right），我们就需要交换这两个元素，使得父节点的值小于或等于子节点的值，从而维持堆的性质。
2. 在建立大顶堆的过程中，我们需要保证父节点的值大于或等于子节点的值。如果父节点的值小于子节点的值（即 left < right），我们就需要交换这两个元素，使得父节点的值大于或等于子节点的值，从而维持堆的性质。

所以，**在堆排序中，我们是通过比较和可能的交换来维持堆的性质，而不是像快速排序那样直接通过比较函数来改变排序的方向。**这就是为什么在建堆过程中，“左大于右就会建立小顶堆，右大于左反而建立大顶堆”。