692. 前K个高频单词 - 力扣（LeetCode）

class SolutionHeap
{
public:
    struct Compare
    {
        bool operator()(const pair<string, int> &v1, const pair<string, int> &v2)
        {
            return v1.first < v2.first || (v1.first == v2.first && v1.second > v2.second);
        }
    };

    vector<string> topKFrequent(const vector<string> &words, int k)
    {
        map<string, int> m;
        for (auto &e : words)
        {
            m[e]++;
        }
        vector<string> v;
        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> pq(m.begin(), m.end());
        for (int i = 0; i < k; i++)
        {
            v.push_back(pq.top().first);
            pq.pop();
        }
        return v;
    }
};

优先级队列是什么样的，为什么要传这些参数？

第1个参数：T——表示队列里的每个元素是什么

pair<string, int>

• 表示队列里的每个元素是 (单词, 出现次数) 这样的键值对。
• 比如 ("apple", 3)、("banana", 2)。

第 2 个参数：Container —— 底层用什么容器存

vector<pair<string, int>>

• priority_queue 不是自己实现存储，而是依赖一个底层容器（默认是 vector）。
• 底层容器需要支持：
  • push_back（插入元素），pop_back（删除元素），front/back（访问首尾），随机访问（堆排序需要）
• 为什么用 vector
  • 连续内存，随机访问快，适合做堆排序。（迭代器为随机迭代器）
  • deque 也可以，但 vector 更常用。

3. 第 3 个参数：Compare —— 比较规则（决定是大顶堆还是小顶堆）

• 它决定了堆的排序规则，默认是 less<T>，表示 “大顶堆”。
• 注意：Compare 是一个仿函数，返回 true 表示 “第一个参数应该排在第二个参数的后面”。

但这里的默认Compare实现不了目的，要自定义仿函数

bool operator()(const pair<string, int>& a, const pair<string, int>& b)；

参数为要比较的元素类型pair<string,int>，而非vector<pair<string,int>>；因为它不会拿两个 vector 去比较只会拿两个元素比较。

仿函数到底是怎么重载、怎么被 sort /priority_queue 自动调用的?

仿函数是怎么调用的

struct kvCompare
{
    bool operator()(const pair<string, int> &kv1, const pair<string, int> &kv2)
    {
        return kv1.second > kv2.second;
    }
};

第一步：创建仿函数对象

kvCompare cmp;  

第二步：像函数一样用 () 调用

pair<string,int> a = {"apple", 2};
pair<string,int> b = {"banana", 5};

// 本质就是调用：cmp.operator()(a, b)
bool res = cmp(a, b);

这就是仿函数的本质：结构体对象.operator ()(参数)

对象(a,b) === 自动变成 ===> 对象.operator()(a,b)

sort 内部大概这样：

while(...)
{
    auto cmp = 你传的比较器;
    if (cmp(a, b)) {  //  这里就是调用 operator()
        swap(a,b);
    }
}

源代码中要用到比较的地方不是直接用大于小于号，而是调用仿函数

核心疑问

1. map 迭代器是从小到大有序遍历（中序遍历）的，传给 priority_queue 构造函数，为什么最后堆能变成大顶堆 / 小顶堆
2. 最后 pq.top() 为什么能直接拿到最大 / 最小，push_back 到底怎么拿到正确结果的

不管传入的迭代器是什么顺序priority_queue 都会自动重新建堆

遍历顺序 → 完全不影响堆的最终结构

1. map 迭代器是有序的，但传给堆没用

priority_queue<..., Compare> pq(m.begin(), m.end());

这句话执行时，内部做了两件事：

1. 把所有元素拷贝到底层 vector（顺序和 map 一样）
2. 调用 make_heap 重建堆→ 完全打乱顺序，按照你的 Compare 规则重新排

所以：map 有序无序 → 对堆没有任何影响。堆只认 Compare 规则，不认传入顺序

#include <iostream>
#include <vector>
#include <algorithm> // 只用swap
using namespace std;

template <class T, class Compare>
void adjustDown(vector<T>& v, int parent, int size, Compare comp)
{
    int child = 2 * parent + 1; // 左孩子

    while (child < size)
    {
        // 找出 左/右 中更需要上浮的孩子
        if (child + 1 < size && comp(v[child], v[child + 1]))
        {
            child++;
        }

        // 父节点 与 最优孩子 比较
        if (comp(v[parent], v[child]))
        {
            swap(v[parent], v[child]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

template <class T, class Compare>
void my_make_heap(vector<T>& v, Compare comp)
{
    int size = v.size();
    if (size <= 1) return;

    // 从最后一个非叶子节点开始，向前逐个向下调整
    for (int i = (size - 2) / 2; i >= 0; --i)
    {
        adjustDown(v, i, size, comp);
    }
}

#include <iostream>
#include <vector>
#include <map>
#include <algorithm> // 这里有 make_heap
using namespace std;

template <class T, class Container = vector<T>, class Compare = less<T>>
class MyPriorityQueue {
private:
    Container c;
    Compare comp;

public:
    // 迭代器构造 —— 完全和STL一样！
    template <class InputIterator>
    MyPriorityQueue(InputIterator first, InputIterator last) {
        // 1. 拷贝数据
        c.assign(first, last);

        // 2. 直接调用 make_heap 建堆！！
        make_heap(c.begin(), c.end(), comp);
    }

    T& top() {
        return c.front();
    }

    void push(const T& x) {
        c.push_back(x);
        push_heap(c.begin(), c.end(), comp);
    }

    void pop() {
        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
    }

    int size() {
        return c.size();
    }
};

assign

assign(first, last)

就是：清空原来容器，再把 [first, last) 区间所有元素，全部复制进来

1. 函数原型（vector）

template <class InputIt>
void assign(InputIt first, InputIt last);

作用：

1. 清空 vector 原来所有内容
2. 遍历 first ~ last 迭代器范围
3. 逐个拷贝，放进当前 vector

2. 和循环 push_back 完全等价

c.assign(first, last);

等价于手写：

c.clear();
while (first != last)
{
    c.push_back(*first);
    first++;
}

注意这样不会改变传过来的实参，因为assign是拷贝值！

得到堆排后的数组

 my_priority_queue::my_pq<int> pq(v.begin(), v.end());
    for (auto &e : pq)
    {
        cout << e << " ";
    }

但要自己实现迭代器

// 迭代器接口，支持范围for循环
auto begin() { return c.begin(); }
auto end() { return c.end(); }

// const版本，支持const对象遍历
auto begin() const { return c.begin(); }
auto end() const { return c.end(); }

或者给类里加一个 print() 成员函数，然后在main函数里通过对象调用

public:
    void print() const
    {
        for (auto& e : c)
        {
            cout << e << " ";
        }
        cout << endl;
    }

错误

第一种（普通类 + 模板函数）

struct Less
{
    template <class T>
    bool operator()(const T &a, const T &b)
    {
        return a < b;
    }
};

• Less 本身就是一个类型
• 它的 operator() 可以接受任意类型 T

Less cmp;        // 直接用
cmp(1, 2);       // 比 int
cmp(1.5, 2.5);   // 比 double
cmp("a", "b");   // 比 string

2. 第二种（模板类）

template <class T>
struct Less
{
    bool operator()(const T &a, const T &b)
    {
        return a < b;
    }
};

• Less 不是类型，Less<int> 才是类型
• 一个实例只能比固定类型 T

Less<int> cmp;    //必须写 <int>
cmp(1, 2);        //只能比 int

Less<double> cmp2;
cmp2(1.5, 2.5);

3. 用在 priority_queue 的区别

template <class T, class Container = vector<T>, class Compare = Less>

template <class T, class Container = vector<T>, class Compare = Less<T>>

在 C++ 里，写 模板类（第二种）更好、更标准、更安全

模板类 less<T> 只能比较 同一种类型 T

• less<int> 只能比 int
• less<string> 只能比 string

不会出现乱七八糟的隐式转换，不会容易出错

错误

my_pq 类里的模板重复了

template <class T, class Container = vector<T>, class Compare = less>
class my_pq
{
public:
    template <class T, class Compare>
    // ...
};

这里 class my_pq 已经定义了 T 和 Compare，在类内部再写 template <class T, class Compare> 是重复定义，会编译报错。（第一个位置是类模板，第二个是函数模板）

比较时传参的顺序

先背死一条 STL 铁律

comp(a, b)
// true 代表：a 比不上 b → a 该下沉，b 该上浮

1. 选左右孩子时（横向对比）

固定：左孩子，右孩子

// right 存在 且 左比不上右
if (right < size && comp(leftChild, rightChild))
      选右孩子

顺序：comp(左 , 右)

2. 父亲 和 最优孩子 对比（纵向对比）

固定：父亲，孩子

// 父亲比不上孩子
if (comp(father, bestChild))
{
    swap(父亲, 孩子);
    父亲下沉，孩子上浮
}

顺序 comp(父 , 子)

两套顺序 永远不变

1. 左右比：comp(左 , 右)
2. 父子比：comp(父 , 子)

不管你是 less /greater、大顶堆 / 小顶堆参数顺序完全不用改！

举例子

大顶堆：comp = less<>

comp(a,b) → a < b

• 左右：comp(左,右) 为 true ⇒ 右更大
• 父子：comp(父,子) 为 true ⇒ 子更大 ⇒ 交换上浮

小顶堆：comp = greater<>

comp(a,b) → a > b

• 左右：comp(左,右) 为 true ⇒ 右更小
• 父子：comp(父,子) 为 true ⇒ 子更小 ⇒ 交换上浮