Python中的Heapq自定义谓词

引言

heap queue 算法，有时也称为优先队列算法，在 Python 的 heapq 模块中实现。它非常适合需要优先排序的任务，因为它能够有效地对集合中的最小元素进行插入、删除和访问。默认情况下，heapq 以最小堆结构排列元素，其中最小元素始终位于根部。

如果您想修改此行为，例如，在处理复杂对象或非标准排序标准时，可以通过修改元素的比较来创建自定义谓词。由于其可定制性，heapq 可用于各种任务，包括调度、路径查找和任何需要优先排序的场景，同时利用其 O(log n) 的插入和提取时间复杂度。

heapq 模块中的几个函数接受列表作为输入，并以最小堆顺序对其进行排序。这些函数存在一个问题，因为它们的参数期望是列表或元组列表。它们不支持与其他对象或可迭代对象进行比较。例如，考虑一个需要保留在堆中的字典。

示例

输出

 
TypeError: heapify() argument must be list, not dict   

heapify() 函数期望参数是列表。如果我们查看字典列表，会发生什么情况。

示例

输出

 
TypeError: '<' not supported between instances of 'dict' and 'dict'   

因此，我们无法使用 heapq 模块来比较两个字典。有时，我们必须将类的对象保留在堆中并对其进行比较。使用此模块，也无法比较此类对象。

示例

本文将介绍上述问题的解决方案。

自定义 heapq 中的排序

heapq 模块中函数的参数可以是项目列表或元组列表。因此，有两种方法可以修改排序过程：

• 要创建用于比较的元组列表或列表，请转换可迭代对象。
• 构建一个重写“<”运算符的包装类。

转换为项目列表

这种简单的方法可以用来解决字典比较问题。在将字典元素转换为元组列表后，可以调用 heapify 方法。

示例 1：简单字典

输出

 
Before organizing as heap: [('p', 'pear'), ('o', 'orange'), ('b', 'banana'), ('g', 'grape'), ('m', 'mango'), ('a', 'apple')]
After organizing as heap: [('a', 'apple'), ('g', 'grape'), ('b', 'banana'), ('o', 'orange'), ('m', 'mango'), ('p', 'pear')]
Resultant dictionary: {'a': 'apple', 'g': 'grape', 'b': 'banana', 'o': 'orange', 'm': 'mango', 'p': 'pear'}   

说明

此代码展示了如何在 Python 的 heapq 模块中使用字典来安排字典为最小堆。使用列表推导式，字典 fruit_dict 首先被转换为元组列表。之后，使用 heapify 函数根据键按字典顺序对列表进行排序。在堆化之后，从列表中创建一个字典。最终结果是一个字典，其条目排列以对应于堆的顺序。

示例 2：字典列表

输出

 
Before organizing as heap: [('p', 'pear'), ('o', 'orange'), ('b', 'banana'), ('g', 'grape'), ('m', 'mango'), ('a', 'apple')]
After organizing as heap: [('a', 'apple'), ('g', 'grape'), ('b', 'banana'), ('o', 'orange'), ('m', 'mango'), ('p', 'pear')]
Resultant dictionary: {'a': 'apple', 'g': 'grape', 'b': 'banana', 'o': 'orange', 'm': 'mango', 'p': 'pear'}

说明

此 Python 程序创建一个字典列表的最小堆，然后将其还原为字典。第一步是生成一个不同的水果字典列表，每个字典包含一个与水果名称对应的键值对。之后，列表被转换为元组列表，其中每个元组包含一个值（水果名称）和一个键（水果的首字母）。此列表使用 heapq.heapify() 方法重新排列为最小堆，将最小的元素（按字母顺序）放在前面。堆化后，列表被重新转换为字典，显示堆顺序中的内容。结果显示了最小堆结构以及数据在堆化之前和之后的更改。

上述方法可用于任何数据类型的字典。

如何使用包装类？

设想一种场景，其中一个类的对象必须保留在一个最小堆中。例如，我们有一个具有以下属性的类：“name”（姓名）、“designation”（职位）、“years of service”（服务年限）和“salary”（薪水）。该类的对象必须根据“yos”（服务年限）保留在最小堆中。

在这种情况下，我们重写关系运算符“<”，使其评估每个员工的服务年限并返回 true 或 false。heapq 模块根据返回的布尔值将对象以最小堆顺序排列。

示例

输出

 
Student Name: Eva
Grade: 9th
Years in School: 2
Annual Fees: 18000

Student Name: John
Grade: 10th
Years in School: 4
Annual Fees: 20000

Student Name: Mark
Grade: 11th
Years in School: 5
Annual Fees: 22000

Student Name: Lisa
Grade: 12th
Years in School: 6
Annual Fees: 25000   

说明

此 Python 程序展示了如何使用 Student 对象列表来生成自定义最小堆。Student 类包含姓名、成绩、在校年限和年费等要素。学生根据在校年限（years）在堆中排序，程序重写了小于（__lt__）比较运算符。使用 heapq 模块将学生对象列表转换为最小堆，在校年限最少 Thus, we are unable to use the heapq module to compare two dictionaries. There may be instances when we must maintain objects of a class in a heap while comparing them. With this module, it is also not possible to compare such things.的学生排在前面。堆形成后，程序会遍历堆，并根据在校年限打印每个学生的信息。

结论

Python heapq 模块提供了一种快速简便的方法来实现具有最小堆的优先队列，从而可以快速插入和提取最小的元素。然而，它可能无法直接处理字典或自定义对象等更复杂的数据类型，因为它主要与列表和元组一起使用。通过使用谓词来自定义排序标准，您可以为各种活动定制 heapq。实现此自定义的一种方法是重写自定义类中的比较运算符，或将不可比较的数据结构转换为元组列表。由于其适应性，heapq 可用于解决资源分配、调度和路径查找等需要优先排序的问题。