STL优先队列实现与逆序排列技巧

"这篇文章除了介绍STL中的优先队列用法，还通过一个简单的C++程序展示了如何自定义比较函数以实现降序排列的优先队列。" 在C++的STL（标准模板库）中，优先队列（priority_queue）是一种特殊的容器，它的行为类似于一个堆，总是保持堆的特性，即最大的元素总是在队列的顶部（默认情况下）。当插入元素时，不会按照先进先出（FIFO）原则进行，而是根据优先级进行排序。在描述中提到，如果希望默认按照降序排列元素，有两种方法： 1. **自定义运算符**：你可以定义一个比较函数对象，重载`>`运算符，使得在比较时反向进行。例如，创建一个名为`cmp`的结构体，并在其中定义`bool operator()(const int &i, const int &j)`，使得当`i > j`时返回`true`，这样在插入元素时，优先队列会认为较大的值优先级更高。 2. **内置函数**：STL提供`greater`和`less`两个函数对象，它们分别代表降序和升序。可以直接使用`priority_queue<int, vector<int>, greater<int>> que1;`来创建一个降序排列的优先队列，这里的`greater<int>`就是内置的降序比较函数。 文章中的代码示例展示了这两种方法的使用。在`main`函数中，创建了两个优先队列，一个使用默认的升序排列，另一个使用自定义的`cmp`结构体进行降序排列。然后，随机生成20个介于0到100之间的整数并插入队列，随后逐个弹出并打印队列顶部的元素，以此展示两种不同排列方式的优先队列的工作原理。 这段代码中，`priority_queue<int> que;`创建了一个默认的优先队列，而`priority_queue<int, vector<int>, cmp> que1;`则使用了自定义比较函数`cmp`。通过`push`方法将随机生成的数字添加到队列，然后使用`top`方法获取并打印最大值，最后通过`pop`方法移除已处理的元素。 总结一下，STL的优先队列提供了灵活的排序方式，用户可以通过自定义比较函数或利用内置函数对象来改变元素的排列顺序，以满足不同的需求。在实际编程中，优先队列常用于需要快速访问最高优先级元素的场景，如Dijkstra算法、Prim算法等。