具有自定义比较谓词的heapq

具有自定义比较谓词的heapq

根据heapq文档，自定义堆顺序的方法是使堆上的每个元素成为一个元组，第一个元组元素是一个接受常规Python比较的元素。

heapq模块中的函数有点麻烦（因为它们不是面向对象的），并且始终需要将我们的堆对象（一个堆化的列表）作为第一个参数显式传递。通过创建一个非常简单的包装器类，我们可以指定一个

key

函数，并将堆显示为一个对象，从而用一块石头杀死两只鸟。

下面的类保留一个内部列表，其中每个元素是一个元组，其第一个成员是一个键，在元素插入时使用

key

参数在Heap实例化时传递该键：

# -*- coding: utf-8 -*-import heapqclass 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失败）