Python heapq模块，对象的heapify方法

Question

因为我想在我正在做的这个程序中提高效率，所以我打算使用Python自带的heapq模块。但是我有些对象有多个属性，比如名字和数字。有没有办法根据某个特定的属性来使用heapify方法对我的对象进行堆排序呢？我在文档里没有找到相关的信息。

Answer 1

@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)

你实际上想用一个包含两个值的元组来作为堆的元素——这个想法是把你想要排序的属性放在元组的第一个值，第二个值还是对象（和之前一样）：

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

这个 heap 会把元组的第一个值当作排序的依据。

• 如果推入 heap 的元素不是简单的数据类型，比如 int 或 str，那么底层的实现需要知道如何比较这些元素。
• 如果元素是一个可迭代对象，元组的第一个元素会被认为是排序值。
• 可以在这里查看示例： https://docs.python.org/3/library/heapq.html#basic-examples（搜索 tuple）

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

---

另一种选择是让比较适用于你的自定义类——这可以实现，使得对象本身可以作为堆的元素（就像第一个例子中那样）。

• 可以在这里查看参考和示例： “为类启用比较”
• 看看增强版的类 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)

Answer 2

我刚发完帖子，就想到你可以先根据需要的属性，把对象整理成一个列表，然后再使用堆化，这样的操作只需要O(n)的线性时间。这不会影响堆化或其他heapq方法的运行时间。