为了账号安全,请及时绑定邮箱和手机立即绑定

具有自定义比较谓词的heapq

/ 猿问

具有自定义比较谓词的heapq

扬帆大鱼 2019-12-26 09:26:32

我正在尝试使用自定义排序谓词构建堆。由于输入的值属于“用户定义”类型,因此我无法修改其内置比较谓词。


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


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

h = heapq.heappush(h, key=my_lt_pred)

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


查看完整描述

3 回答

?
慕姐4208626

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


heapq模块中的函数有些麻烦(因为它们不是面向对象的),并且始终需要将我们的堆对象(一个堆化的列表)作为第一个参数显式传递。通过创建一个非常简单的包装器类,我们可以指定一个key函数,并将堆显示为一个对象,从而用一块石头杀死两只鸟。


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


# -*- coding: utf-8 -*-

import heapq


class MyHeap(object):

   def __init__(self, initial=None, key=lambda x:x):

       self.key = key

       if initial:

           self._data = [(key(item), item) for item in initial]

           heapq.heapify(self._data)

       else:

           self._data = []


   def push(self, item):

       heapq.heappush(self._data, (self.key(item), item))


   def pop(self):

       return heapq.heappop(self._data)[1]


查看完整回答
反对 2019-12-26
?
慕哥9229398

所述heapq文档表明,堆元件可以是元组,其中所述第一元件是所述优先级,并限定的排序顺序。


但是,与您的问题更为相关的是,该文档中包含有关示例代码的讨论,该示例代码说明了如何实现自己的heapq包装函数来处理排序稳定性和具有相同优先级的元素(以及其他问题)的问题。


简而言之,他们的解决方案是使heapq中的每个元素都是三元组,并具有优先级,条目计数和要插入的元素。条目计数确保具有相同优先级的元素按照添加到heapq的顺序进行排序。


查看完整回答
反对 2019-12-26
?
慕容4345310

这两个答案的局限性在于它们不允许将领带视为领带。在第一个中,通过比较项目来打破联系,在第二个中,通过比较输入顺序来打破关系。让领带成为领带会更快,而且如果领带很多,这可能会带来很大的不同。基于上面和文档,尚不清楚是否可以在heapq中实现。奇怪的是,heapq不接受键,而在同一模块中从它派生的功能却接受。
PS:如果您点击第一个评论中的链接(“可能重复...”),那么还有另一种定义le的建议,这似乎是一种解决方案。

查看完整回答
反对 2019-12-26

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信