C++ 优先队列priority_queue（同一优先级数据顺序）

admin管理员组

文章数量:1623787

一、介绍

priority_queue是C++标准库中提供的一种容器适配器，它提供了一种存储和操作元素的方式，确保优先级最高的元素始终位于队列的前面。它可以在运行时自动地保持其元素有序。其内部实现了一个堆（heap），具有以下性质：

最大堆（max heap）：根节点的值大于等于其子节点的值。
最小堆（min heap）：根节点的值小于等于其子节点的值。

priority_queue中的元素根据它们的优先级进行排序，这是由在声明时提供的比较函数决定的。默认情况下，priority_queue使用std::less按升序排序元素，其中T是被存储元素的类型。

priority_queue容器支持以下操作：

push(): 将新元素插入到优先级队列中。
pop(): 从优先级队列中删除最高优先级的元素。
top(): 返回位于队列前面的最高优先级的元素。
empty(): 检查优先级队列是否为空。
size(): 返回优先级队列中元素的数量。
需要注意的是，priority_queue并不提供遍历容器中所有元素的方式，因为它被设计为只允许访问位于队列前面的最高优先级的元素。如果需要遍历所有元素，可以将priority_queue的元素复制到另一个容器中进行遍历。

参数说明：

std::priority_queue<T, Container, Compare>

其中，T 表示队列中元素的类型；Container 表示内部容器的类型，默认情况下是 std::vector；Compare 是一个可选的比较函数对象，用来指定元素的比较规则，如果不指定，则默认使用 std::less 来进行比较。

下面分别介绍 Container 和 Compare 两个参数。

Container
Container 是一个用于存储元素的内部容器类型，默认为 std::vector。它必须提供以下几个方法：

front()：返回队列中第一个元素的引用。
push_back(const T& x)：将元素 x 添加到容器的末尾。
pop_back()：删除容器末尾的元素。
size()：返回容器中元素的个数。
除了 std::vector，还可以使用其他类型的容器，例如 std::deque，或者用户自定义的容器类型。

Compare
Compare 是一个可选的比较函数对象，用来指定元素的比较规则。如果不指定，则默认使用 std::less 来进行比较，即使用 < 运算符来比较元素大小。如果想要创建一个最小堆，则可以指定 Compare 为 std::greater，即使用 > 运算符来比较元素大小。

比较函数对象需要实现一个接受两个元素的参数，返回一个 bool 类型的结果，表示第一个元素是否小于（或大于）第二个元素。例如：

struct Compare {
    bool operator()(const T& lhs, const T& rhs) {
        // 比较 lhs 和 rhs 的大小关系，返回结果
    }
};

当我们指定 Compare 为 struct Compare 时，我们需要自己实现比较函数 operator()，来定义元素的比较规则。

二、demo

#include <queue>
#include <iostream>

using namespace std;

int main() {
    priority_queue<int> max_heap;

    // Insert elements into the heap
    max_heap.push(10);
    max_heap.push(20);
    max_heap.push(15);

    // Print the largest element in the heap
    cout << "Largest element in the heap: " << max_heap.top() << endl;

    // Remove the largest element from the heap
    max_heap.pop();

    // Print the new largest element in the heap
    cout << "New largest element in the heap: " << max_heap.top() << endl;

    return 0;
}

输出结果：

Largest element in the heap: 20
New largest element in the heap: 15

三、自定义排序

#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <functional> 
using namespace std;
struct data_info
{
    string data;
    int line;
};

struct cmp1
{
	bool operator () (data_info a,data_info b)		  
	{
		return a.line < b.line; 	
	}
};

void test_priority_queue()
{

    priority_queue<data_info, vector<data_info>, cmp1> data_queue; 
    data_queue.push({"123", 0});
    data_queue.push({"852", 1});
    data_queue.push({"2341", 2});
    data_queue.push({"789", 1});
    data_queue.push({"1233", 0});
    data_queue.push({"963", 1});
    data_queue.push({"1232", 0});
    data_queue.push({"756", 1});
    data_queue.push({"2342", 2});
    data_queue.push({"1231", 0});
    data_queue.push({"234", 2});

    
    data_queue.push({"741", 2});

    while(!data_queue.empty())
    {
        cout << data_queue.top().data << " "  << data_queue.top().line<< endl;
        data_queue.pop();
    }
        

}
int main()
{
	test_priority_queue();
	return 0;
}

输出结果

2341 2
741 2
2342 2
234 2
852 1
963 1
789 1
756 1
1232 0
1233 0
1231 0
123 0

需要注意的是：如果priority_queue中有多个元素具有相同的优先级，它们的排列方式是不确定的。这是因为priority_queue使用堆数据结构来维护元素的优先级，堆的性质决定了同一优先级的元素之间没有明确的顺序。

在默认情况下，priority_queue使用std::less作为比较函数来比较元素的优先级，这将导致具有相同优先级的元素以相反的顺序排列，即后插入的元素将排在前面。如果需要更精确的控制元素之间的顺序，可以提供自定义比较函数来指定元素之间的优先级关系。

本文标签： 优先级队列顺序数据priorityqueue