C++ 中按第一个和第二个元素排序的对优先队列

引言

优先队列是计算机科学中的一种基本数据结构，可以快速访问优先级最高（或最低）的元素。C++ 中的优先队列可以扩展以处理 pair，从而提供一种根据 pair 的第一个或第二个元素进行排序的灵活方法。本文将深入探讨 C++ 中优先队列 pair 的使用细节，并解释如何构建自定义比较器以按第一个或第二个元素排序。

理解优先队列

优先队列是一种数据结构，它跟踪具有优先级的多个元素。然后，它可以快速检索优先级最高（或最低）的元素。C++ 中的 头文件提供了 priority_queue 模板，可以方便地实现优先队列。优先队列是一个容器，可以不断检索优先级最高（或最低）的元素。C++ 中的 priority_queue 容器适配器使用堆来管理元素，从而可以在恒定的时间内检索最大（默认）或最小元素。

优先队列 pair 的基本用法

在使用 pair 的优先队列之前，必须先定义 pair 类型。然后，必须使用正确的模板参数声明优先队列。例如：

输出

代码解释

头文件包含

• 这些行包含了所需的头文件。它们用于使用 priority_queue 容器以及进行输入和输出操作。

命名空间声明

• 此行允许您使用标准的 C++ 库元素，而无需在它们前面加上 std:: 前缀。

主函数

• 程序的入口点，从这里开始执行。

优先队列声明

• 创建一个名为 pq 的优先队列来存储整数 pair。默认情况下，pair 按第一个元素降序排列。

将 pair 推入优先队列

• push 方法用于将整数 pair 推入优先队列。

打印和弹出元素

• 只要优先队列不为空，此 while 循环将继续运行。在循环内：
• 使用 pq.top() 获取优先级最高（按第一个元素降序排列）的 pair。
• Cout 打印 pair 的第一个和第二个元素。
• 使用 pq.pop() 从优先队列中删除优先级最高的元素。

Return Statement (返回语句)

• 表明程序已成功执行。

优先队列的自定义比较器

为排序容器（如优先队列）中的元素定义自定义比较器是 C++ 最强大的功能之一。当我们希望根据第二个元素进行排序或使用自定义逻辑时，这对于 pair 来说至关重要。您可以定义一个自定义比较器，以使用自定义逻辑或基于第二个元素来排序 pair。比较器是一个类或结构，通过重载 operator() 来提供所需的比较逻辑。自定义比较器的一个可能应用是按第二个元素升序排列 pair。

输出

代码解释

自定义比较器的定义

• ComparePairs 结构体的目的是充当 pair 的唯一比较器。
• 为了指定比较逻辑，它会重载 operator()。
• 在这里，pair（a.first 和 b.first）是根据它们的第一个元素进行比较的。

使用自定义比较器声明优先队列

• 在声明 priority_queue 时使用的模板参数中指定了 pair 类型（std::pair）、底层容器（std::vector>）和自定义比较器（ComparePairs）。
• 这会根据 ComparePairs 结构体中指定的逻辑修改优先队列的排序行为。

pair 按如下方式添加到优先队列：

• push 方法将 pair 推入优先队列。
• 由于元素会根据自定义比较器自动重新排列，因此插入顺序不会影响优先队列的顺序。

打印和弹出元素

• 只要优先队列不为空，while 循环就会继续运行。
• 在循环内，使用自定义比较器，pq.top() 获取优先级最高的 pair。
• Cout 打印 pair 的第一个和第二个元素。
• 使用 pq.pop() 从优先队列中删除优先级最高的元素。

返回语句

• 表示程序已成功执行。

按第二个元素排序

相应地调整自定义比较器以根据第二个元素确定 pair 的顺序：

输出

代码解释

包含

• ：提供输入和输出功能。
• ：包含 priority_queue 容器的定义。
• ：包含 vector 容器的定义。

命名空间

• 使用 using namespace std; 语句，可以不带 std:: 前缀地使用标准 C++ 实体。

自定义仿函数

• ComparePairsBySecond 结构体中定义的仿函数包含一个重载的 operator()。
• 此仿函数用于比较优先队列中的 pair。它使用每个 pair 的第二个元素进行比较，该元素将在优先队列中排名较低。

优先队列声明

• vector>, priority_queue, vector>, ComparePairsBySecond> pq; 使用 ComparePairsBySecond 仿函数提供的自定义比较逻辑声明一个整数 pair 的优先队列。

将元素推入优先队列

• 以下 pair 被推入优先队列：{3, 10}, {1, 5}, {2, 8}, 和 {4, 2}。

处理和打印

• 然后，代码进入一个 while 循环，该循环一直运行直到优先队列为空。
• 在每次迭代中，使用 cout 打印优先队列中第二个元素最大的 pair。
• 然后调用 pop() 函数删除优先队列中的顶层元素。

输出

• 程序的输出将是按第二个元素降序打印的 pair。

高级技术

优先队列 pair 的使用可以超越基础知识，应用于各种高级场景。根据用例，可以使用高级方法。这些方法包括使用不同数据类型的 pair、修改复杂场景的比较逻辑以及构建最小堆而不是最大堆。让我们研究一些方法：

自定义排序逻辑

为了支持复杂的排序标准，可以进一步修改自定义比较器的比较逻辑。例如，考虑在按字典序对 pair 进行排序时同时考虑第一个和第二个元素。字典序是一种常见的用法，其中 pair 根据第一个元素排序，如果第一个元素相等，则根据第二个元素排序。为此，请定义一个考虑这两个元素的自定义比较器。

此比较器按字典序对 pair 进行排序，如果它们相等，则根据第一个元素排序，否则根据第二个元素排序。

使用不同数据类型的 pair

pair 的第一个和第二个元素可以包含各种数据类型。例如，您的优先队列中可能有一个整数和一个字符串的 pair。pair 可以包含两个组件的不同数据类型。例如，一个 pair 可能包含一个字符串和一个整数。自定义比较器需要仔细处理异构类型的比较。

在这些情况下，自定义比较器需要正确处理异构类型比较。

构建最小堆

Priority_queue 默认构建最大堆。如果需要最小堆，可以调整自定义比较器。

此比较器使用第一个元素，如果需要，还使用第二个元素来生成最小堆。