Python heapq 模块，对象上的 heapify 方法

Question

因为我试图在我正在制作的程序中提高效率，所以我想我应该使用 python 中内置的 heapq 模块，但是我的一些对象具有多个属性，例如名称和编号。有没有办法使用 heapify 方法根据某个属性来堆化我的对象？我在文档中没有看到任何内容。

Answer 1

在我发布之后，我想你可以在使用 heapify 之前根据所需的属性创建一个对象列表，这将花费 O(n) 线性时间。这不会影响 heapify 或其他 heapq 方法的运行时。

Answer 2

@vsekhar 和@所有其他人都想知道已接受的答案。

假设：

class SomeObject():
    def __init__(self,name, number):
        self.name = name
        self.number = number

a_list = []
obj_1 = SomeObject("tim", 12)
obj_2 = SomeObject("tom", 13)

现在，不是创建一个仅将对象作为元素的堆：

heapq.heappush(a_list, obj_1)
heapq.heappush(a_list, obj_2)

您实际上想要创建一个包含 2 个值的元组作为堆元素的堆 - 这个想法是将要排序的属性作为该属性的第一个值元组和对象（如前所述）作为元组的第二个元素：

# Sort by 'number'.
heapq.heappush(a_list, (obj_1.number, obj_1))
heapq.heappush(a_list, (obj_2.number, obj_2))

堆将元组的第一个值视为排序依据的值。

• 如果推送到heap的元素不是像int或str这样的简单数据类型，底层实现需要知道如何比较元素。
• 如果元素是可迭代的，则第一个元素被视为包含排序值。
• 看看这里的例子：https://docs.python。 org/3/library/heapq.html#basic-examples（搜索元组）

堆元素可以是元组。这对于在跟踪的主记录旁边分配比较值（例如任务优先级）非常有用：

---

另一个选项可能是使比较与您的自定义类一起工作 - 可以实现此操作，以便对象本身可以用作堆元素（如在第一个例子中）。

• 请参阅此处以获取参考和示例：“启用”类比较
• 看看增强类 SomeObject：

class SomeObject():
    def __init__(self,name, number):
        self.name = name
        self.number = number
    def __eq__(self, obj): 
        return self.number == obj.number 
    def __lt__(self, obj): 
        return self.number < obj.number 
    def __hash__(self): 
        return hash(self.number)

这样您就可以创建仅将对象作为元素的堆：

heapq.heappush(a_list, obj_1)
heapq.heappush(a_list, obj_2)