C++中priority_queue存储3元素方法及模板参数疑问解答

我近期在LeetCode平台学习C++的priority_queue相关用法，查阅题解时看到一段示例代码，我能判断其实现的是最小堆，但无法理解代码是如何向minHeap中存储3个元素的，具体疑问如下：

1. 是否是vector<int>接收matrix[r][0]、vector<vector<int>>接收r、greater<>接收0？
2. 为什么通过priority_queue<int,vector<int>,greater<int>> minHeap定义最小堆时，需要传入vector<int>作为模板参数？

回答 #

针对第一个疑问

你把模板参数和实际存储的元素完全搞混了。
你看到的能存3个值的最小堆，元素类型本身就是长度为3的序列（一般是vector<int>或者tuple<int,int,int>），每个元素里依次存三个信息：矩阵里的元素值matrix[r][c]、元素所在行号r、元素所在列号c。三个值是打包成一个整体元素存进堆的，不是分别传给三个模板参数。
三个模板参数各有用处，和单个元素里存几个值没有任何关系：greater<>只是比较规则，作用是告诉优先队列要把更小的元素放到堆顶，实现最小堆逻辑，根本不负责存储数据。

针对第二个疑问

priority_queue是容器适配器，本身不实现底层数据存储逻辑，所有元素都存在它包裹的底层容器里，它只负责在底层容器之上维护堆结构、提供堆的入堆/出堆/取堆顶接口。
它的标准模板定义如下：

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

三个模板参数的作用分别是：

• T：堆中存储的元素的类型
• Container：底层用来存数据的容器类型，要求支持随机访问、push_back、pop_back、front接口，默认值就是vector<T>，就算你不显式写，编译器也会默认用vector作为底层容器。很多题解显式写出这个参数只是为了代码更直观，减少读者理解成本。
• Compare：堆排序使用的比较函数，默认值less<T>对应大顶堆，传入greater<T>时对应小顶堆。
  你看到的vector<int>就是指定底层存储用的容器类型，和存几个元素、存什么值没有关系。

内容的提问来源于stack exchange，提问作者coding noob