STL优先级队列的比较函数与大堆小堆的关系

STL中的priority_queue（优先级队列）通过比较函数来确定元素的优先级顺序，从而决定其内部是形成大堆还是小堆。以下是关键点总结：

1. 默认行为与大堆：

   • 默认情况下，priority_queue使用std::less<T>作为比较函数，形成大堆（最大堆）。
   • 大堆特性：父节点的值总大于或等于子节点，堆顶元素为最大值。
   • 比较逻辑：当a < b返回true时，认为b的优先级更高，较大的元素会被置于堆顶。

2. 小堆的实现：

   • 若使用std::greater<T>作为比较函数，则形成小堆（最小堆）。
   • 小堆特性：父节点的值总小于或等于子节点，堆顶元素为最小值。
   • 比较逻辑：当a > b返回true时，认为b的优先级更高，较小的元素会被置于堆顶。

3. 比较函数的作用：

   • 比较函数Compare接受两个参数a和b，返回值为true表示第二个参数b的优先级更高。
   • 元素的插入和堆调整均基于此规则，确保堆结构始终符合比较函数定义的顺序。

4. 示例说明：

   // 默认大堆，使用less<T>
   priority_queue<int> max_heap;// 显式小堆，使用greater<T>
   priority_queue<int, vector<int>, greater<int>> min_heap;
   

5. 自定义比较函数：

   • 可通过自定义函数或仿函数定义特殊优先级规则。例如，实现按绝对值大小排列的堆：

   struct AbsCompare {bool operator()(int a, int b) {return abs(a) < abs(b); // 返回true时，b的绝对值更大，优先级更高}
   };
   priority_queue<int, vector<int>, AbsCompare> abs_max_heap;
   

总结：比较函数通过定义元素的优先级顺序（第二个参数是否应优先于第一个参数），直接决定priority_queue是大堆还是小堆。理解比较函数参数的顺序及其返回值对优先级的影响，是正确使用优先级队列的关键。