python - 具有自定义比较谓词的 heapq

Question

我正在尝试使用自定义排序谓词构建堆。由于进入它的值是“用户定义”类型，我无法修改它们的内置比较谓词。

有没有办法做类似的事情:

h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)

或者更好的是，我可以将 heapq 函数包装在自己的容器中，这样我就不需要继续传递谓词了。

Answer 1

根据heapq documentation ，自定义堆顺序的方法是让堆上的每个元素成为一个元组，第一个元组元素是一个接受普通 Python 比较的元素。

heapq 模块中的函数有点麻烦(因为它们不是面向对象的)，并且总是需要我们的堆对象(一个堆化列表)作为第一个参数显式传递。我们可以通过创建一个非常简单的包装类来用一 block 石头杀死两只鸟，它允许我们指定一个 key 函数，并将堆呈现为一个对象。

下面的类保留一个内部列表，其中每个元素都是一个元组，其中第一个成员是一个键，在元素插入时使用 key 参数计算，在堆实例化时传递:

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
    def __init__(self, initial=None, key=lambda x:x):
        self.key = key
        self.index = 0
        if initial:
            self._data = [(key(item), i, item) for i, item in enumerate(initial)]
            self.index = len(self._data)
            heapq.heapify(self._data)
        else:
            self._data = []

    def push(self, item):
        heapq.heappush(self._data, (self.key(item), self.index, item))
        self.index += 1

    def pop(self):
        return heapq.heappop(self._data)[2]

(额外的 self.index 部分是为了避免在评估的键值是平局并且存储的值不能直接比较时发生冲突 - 否则 heapq 可能会因 TypeError 而失败)