带有自定义比较谓词的 heapq [英] heapq with custom compare predicate

问题描述

我正在尝试使用自定义排序谓词构建堆.由于进入其中的值属于用户定义"类型，因此我无法修改它们的内置比较谓词.

I am trying to build a heap with a custom sort predicate. Since the values going into it are of 'user-defined' type, I cannot modify their built-in comparison predicate.

有没有办法做这样的事情:

Is there a way to do something like:

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

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

Or even better, I could wrap the heapq functions in my own container so I don't need to keep passing the predicate.

推荐答案

根据 heapq 文档，自定义堆顺序的方法是让堆上的每个元素都是一个元组，第一个元组元素是一个接受正常Python比较的元组.

According to the heapq documentation, the way to customize the heap order is to have each element on the heap to be a tuple, with the first tuple element being one that accepts normal Python comparisons.

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

The functions in the heapq module are a bit cumbersome (since they are not object-oriented), and always require our heap object (a heapified list) to be explicitly passed as the first parameter. We can kill two birds with one stone by creating a very simple wrapper class that will allow us to specify a key function, and present the heap as an object.

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

The class below keeps an internal list, where each element is a tuple, the first member of which is a key, calculated at element insertion time using the key parameter, passed at Heap instantiation:

# -*- 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 而失败)

(The extra self.index part is to avoid clashes when the evaluated key value is a draw and the stored value is not directly comparable - otherwise heapq could fail with TypeError)

这篇关于带有自定义比较谓词的 heapq的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！