blocks|key|1588075|text|传统的解决方案是在堆上存储(优先级，任务)元组：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1588076|pq+=+[+]
heappush(pq,+(10,+task1))
heappush(pq,+(5,+task2))
heappush(pq,+(15,+task3))
priority,+task+=+heappop(pq)|code-block|syntax|javascript|1588077|只要没有两个任务具有相同的优先级，这就可以很好地工作；否则，将比较任务本身(这在Python3中可能根本不起作用)。|1588078|常规文档给出了如何使用heapq实现优先级队列的指导：|1588079|http://docs.python.org/library/heapq.html#priority-queue-implementation-notes|offset|length|1588080|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|0|0|25|0|0^^$0|@$1|2|3|4|5|6|7|V|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|W|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|X|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|Y|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|Z|8|@]|9|@$M|10|N|11|1|12]]|A|$]]|$1|O|3|-4|5|6|7|13|8|@]|9|@]|A|$]]]|P|$Q|$5|R|S|T|A|$U|L]]]]

The traditional solution is to store (priority, task) tuples on the heap:

<pre><code>pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)
</code></pre>

This works fine as long as no two tasks have the same priority; otherwise, the tasks themselves are compared (which might not work at all in Python 3).

The regular docs give guidance on how to implement priority queues using heapq:

<a href="http://docs.python.org/library/heapq.html#priority-queue-implementation-notes" rel="noreferrer">http://docs.python.org/library/heapq.html#priority-queue-implementation-notes</a>

blocks|key|1802601|text|只需为列表中的对象编写适当的__lt__方法，以便它们正确排序：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1802602|class+FirstList(list):
++++def+__lt__(self,+other):
++++++++return+self[0]+<+other[0]

lst+=+[+['a',+3],+['b',+1]+]

lst+=+[FirstList(item)+for+item+in+lst]|code-block|syntax|javascript|1802603|虽然定义所有比较或使用functools.total_ordering是一个好主意，但Python只需要__lt__进行排序。|1802604|您可以看到，它是通过使用两个具有相同第一值和不同第二值的项来工作的。无论第二个值是什么，当您执行heapify时，这两个对象将交换位置，因为lst[0]+<+lst[1]将始终为False。如果你需要heapify是稳定的，你需要一个更复杂的比较。|1802605|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/2/library/functools.html#functools.total_ordering^0|E|6|0|0|B|O|1G|6|B|O|0|0|1C|7|1Y|F|2H|5|2S|7|0^^$0|@$1|2|3|4|5|6|7|W|8|@$9|X|A|Y|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|Z|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|10|8|@$9|11|A|12|B|C]|$9|13|A|14|B|C]]|D|@$9|15|A|16|1|17]]|E|$]]|$1|M|3|N|5|6|7|18|8|@$9|19|A|1A|B|C]|$9|1B|A|1C|B|C]|$9|1D|A|1E|B|C]|$9|1F|A|1G|B|C]]|D|@]|E|$]]|$1|O|3|-4|5|6|7|1H|8|@]|D|@]|E|$]]]|P|$Q|$5|R|S|T|E|$U|V]]]]

Just write an appropriate <code>__lt__</code> method for the objects in the list so they sort correctly:

<pre><code>class FirstList(list):
 def __lt__(self, other):
 return self[0] &lt; other[0]

lst = [ ['a', 3], ['b', 1] ]

lst = [FirstList(item) for item in lst]
</code></pre>

Only <code>__lt__</code> is needed by Python for sorting, though it's a good idea to define all of the comparisons or use <a href="https://docs.python.org/2/library/functools.html#functools.total_ordering" rel="noreferrer"><code>functools.total_ordering</code></a>.

You can see that it is working by using two items with the same first value and different second values. The two objects will swap places when you <code>heapify</code> no matter what the second values are because <code>lst[0] &lt; lst[1]</code> will always be <code>False</code>. If you need the <code>heapify</code> to be stable, you need a more complex comparison.

blocks|key|1588069|text|这太可怕了，你绝对不应该这么做，…但它看起来像heapq模块defines+a+cmp_lt+function，如果你真的想要一个自定义的比较函数，你可以随意修补它。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1588070|entityMap|0|LINK|mutability|MUTABLE|url|http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l136^0|N|5|14|6|U|P|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@$9|O|A|P|B|C]|$9|Q|A|R|B|C]]|D|@$9|S|A|T|1|U]]|E|$]]|$1|F|3|-4|5|6|7|V|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]]]

Well, this is terrible and awful and you definitely shouldn't do it… But it looks like the <code>heapq</code> module <a href="http://hg.python.org/cpython/file/2.7/Lib/heapq.py#l136" rel="nofollow">defines a <code>cmp_lt</code> function</a>, which you could monkey patch if you really wanted a custom compare function.

blocks|key|1802633|text|我不知道这是不是更好，但它类似于Raymond+Hettinger的解决方案，但优先级是由对象决定的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1802634|假设这是您的对象，并且您希望按x属性进行排序。|1802635|class+Item:+++++++++++++++++++++++++++++++++
++++def+__init__(self,+x):
++++++++self.x+=+x|code-block|syntax|javascript|1802636|然后有一个应用配对的函数|1802637|def+create_pairs(items):
+++++return+map(lambda+item:+(item.x,+item),+items)|1802638|然后将该函数作为heapq.merge的输入应用于列表|1802639|list(heapq.merge(create_pairs([Item(1),+Item(3)]),+
+++++++++++++++++create_pairs([Item(2),+Item(5)])))|1802640|这给了我以下输出|1802641|[(1,+<__main__.Item+instance+at+0x2660cb0>),
+(2,+<__main__.Item+instance+at+0x26c2830>),
+(3,+<__main__.Item+instance+at+0x26c27e8>),
+(5,+<__main__.Item+instance+at+0x26c2878>)]|1802642|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|Z|8|@]|9|@]|A|$]]|$1|K|3|L|5|F|7|10|8|@]|9|@]|A|$G|H]]|$1|M|3|N|5|6|7|11|8|@]|9|@]|A|$]]|$1|O|3|P|5|F|7|12|8|@]|9|@]|A|$G|H]]|$1|Q|3|R|5|6|7|13|8|@]|9|@]|A|$]]|$1|S|3|T|5|F|7|14|8|@]|9|@]|A|$G|H]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

I don't know if this is better but it is like Raymond Hettinger's solution but the priority is determined from the object.

Let this be your object and you want to sort by the the x attribute.

<pre><code>class Item: 
 def __init__(self, x):
 self.x = x
</code></pre>

Then have a function which applies the pairing

<pre><code>def create_pairs(items):
 return map(lambda item: (item.x, item), items)
</code></pre>

Then apply the function to the lists as input into heapq.merge

<pre><code>list(heapq.merge(create_pairs([Item(1), Item(3)]), 
 create_pairs([Item(2), Item(5)])))
</code></pre>

Which gave me the following output

<pre><code>[(1, &lt;__main__.Item instance at 0x2660cb0&gt;),
 (2, &lt;__main__.Item instance at 0x26c2830&gt;),
 (3, &lt;__main__.Item instance at 0x26c27e8&gt;),
 (5, &lt;__main__.Item instance at 0x26c2878&gt;)]
</code></pre>

blocks|key|1802644|text|通过这些Heap和HeapBy类，我试图简化heapq的使用。您可以使用HeapBy来传递一个键排序函数。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1802645|请注意，雷蒙德说，如果优先级重复且值不可排序，则他的solution将不起作用。这就是为什么我添加了一个包含NonComparable类的HeapBy示例。|1802646|我从agf's+solution那里学到了__lt__的想法。|1802647|用法：|1802648|#+Use+HeapBy+with+a+lambda+for+sorting
max_heap+=+HeapBy(key=lambda+x:+-x)
max_heap.push(3)
max_heap.push(1)
max_heap.push(2)
assert+max_heap.pop()+==+3
assert+max_heap.pop()+==+2
assert+max_heap.pop()+==+1

#+Use+Heap+as+a+convenience+facade+for+heapq
min_heap+=+Heap()
min_heap.push(3)
min_heap.push(1)
min_heap.push(2)
assert+min_heap.pop()+==+1
assert+min_heap.pop()+==+2
assert+min_heap.pop()+==+3

# HeapBy+also+works+with+non-comparable+objects.
#+Note+that+I+push+a+duplicated+value
#+to+make+sure+heapq+will+not+try+to+call+__lt__+on+it.

class+NonComparable:
++++def+__init__(self,+val):
++++++++self.val+=+val

#+Using+non+comparable+values
max_heap+=+HeapBy(key=lambda+x:+-x.val)
max_heap.push(NonComparable(1))
max_heap.push(NonComparable(1))
max_heap.push(NonComparable(3))
max_heap.push(NonComparable(2))
assert+max_heap.pop().val+==+3
assert+max_heap.pop().val+==+2
assert+max_heap.pop().val+==+1
assert+max_heap.pop().val+==+1|code-block|syntax|javascript|1802649|类：|1802650|import+heapq

class+Heap:
++++"""
++++Convenience+class+for+simplifying+heapq+usage
++++"""

++++def+__init__(self,+array=None,+heapify=True):
++++++++if+array:
++++++++++++self.heap+=+array
++++++++++++if+heapify:
++++++++++++++++heapq.heapify(self.heap)
++++++++else:
++++++++++++self.heap+=+[]

++++def+push(self,+x):
++++++++heapq.heappush(self.heap,+x)

++++def+pop(self):
++++++++return+heapq.heappop(self.heap)


class+HeapBy(Heap):
++++"""
++++Heap+where+you+can+specify+a+key+function+for+sorting
++++"""

++++#+Item+only+uses+the+key+function+to+sort+elements,
++++#+just+in+case+the+values+are+not+comparable
++++class+Item:
++++++++def+__init__(self,+value,+key):
++++++++++++self.key+=+key
++++++++++++self.value+=+value
++++++++def+__lt__(self,+other):
++++++++++++return+self.key(self.value)+<+other.key(other.value)

++++def+__init__(self,+key,+array=None,+heapify=True):
++++++++super().__init__(array,+heapify)
++++++++self.key+=+key

++++def+push(self,+x):
++++++++super().push(self.Item(x,+self.key))

++++def+pop(self):
++++++++return+super().pop().value|1802651|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/a/7810917/1121497|1|https://stackoverflow.com/a/7803240/1121497^0|4|4|9|6|M|5|10|6|0|1I|D|1X|6|Q|8|0|0|L|6|2|E|1|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@$9|15|A|16|B|C]|$9|17|A|18|B|C]|$9|19|A|1A|B|C]|$9|1B|A|1C|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1D|8|@$9|1E|A|1F|B|C]|$9|1G|A|1H|B|C]]|D|@$9|1I|A|1J|1|1K]]|E|$]]|$1|H|3|I|5|6|7|1L|8|@$9|1M|A|1N|B|C]]|D|@$9|1O|A|1P|1|1Q]]|E|$]]|$1|J|3|K|5|6|7|1R|8|@]|D|@]|E|$]]|$1|L|3|M|5|N|7|1S|8|@]|D|@]|E|$O|P]]|$1|Q|3|R|5|6|7|1T|8|@]|D|@]|E|$]]|$1|S|3|T|5|N|7|1U|8|@]|D|@]|E|$O|P]]|$1|U|3|-4|5|6|7|1V|8|@]|D|@]|E|$]]]|V|$W|$5|X|Y|Z|E|$10|11]]|12|$5|X|Y|Z|E|$10|13]]]]

With these <code>Heap</code> and <code>HeapBy</code> classes I tried to simplify the usage of <code>heapq</code>. You can use <code>HeapBy</code> to pass a key sorting function.

Note that Raymond said that his <a href="https://stackoverflow.com/a/7810917/1121497">solution</a> won't work if priorities are repeated and the values are not sortable. That's why I added an example of <code>HeapBy</code> with a <code>NonComparable</code> class.

I took the <code>__lt__</code> idea from <a href="https://stackoverflow.com/a/7803240/1121497">agf's solution</a>.

Usage:

<pre><code># Use HeapBy with a lambda for sorting
max_heap = HeapBy(key=lambda x: -x)
max_heap.push(3)
max_heap.push(1)
max_heap.push(2)
assert max_heap.pop() == 3
assert max_heap.pop() == 2
assert max_heap.pop() == 1

# Use Heap as a convenience facade for heapq
min_heap = Heap()
min_heap.push(3)
min_heap.push(1)
min_heap.push(2)
assert min_heap.pop() == 1
assert min_heap.pop() == 2
assert min_heap.pop() == 3

# HeapBy also works with non-comparable objects.
# Note that I push a duplicated value
# to make sure heapq will not try to call __lt__ on it.

class NonComparable:
 def __init__(self, val):
 self.val = val

# Using non comparable values
max_heap = HeapBy(key=lambda x: -x.val)
max_heap.push(NonComparable(1))
max_heap.push(NonComparable(1))
max_heap.push(NonComparable(3))
max_heap.push(NonComparable(2))
assert max_heap.pop().val == 3
assert max_heap.pop().val == 2
assert max_heap.pop().val == 1
assert max_heap.pop().val == 1
</code></pre>

Classes:

<pre><code>import heapq

class Heap:
 """
 Convenience class for simplifying heapq usage
 """

 def __init__(self, array=None, heapify=True):
 if array:
 self.heap = array
 if heapify:
 heapq.heapify(self.heap)
 else:
 self.heap = []

 def push(self, x):
 heapq.heappush(self.heap, x)

 def pop(self):
 return heapq.heappop(self.heap)


class HeapBy(Heap):
 """
 Heap where you can specify a key function for sorting
 """

 # Item only uses the key function to sort elements,
 # just in case the values are not comparable
 class Item:
 def __init__(self, value, key):
 self.key = key
 self.value = value
 def __lt__(self, other):
 return self.key(self.value) &lt; other.key(other.value)

 def __init__(self, key, array=None, heapify=True):
 super().__init__(array, heapify)
 self.key = key

 def push(self, x):
 super().push(self.Item(x, self.key))

 def pop(self):
 return super().pop().value
</code></pre>

I'm using python2.6. Is it available in higher version of python? 
Else is there any other way I can maintain priority queues for list of objects of non-trivial classes?
What I need is something like this

<pre><code>&gt;&gt;&gt; l = [ ['a', 3], ['b', 1] ]
&gt;&gt;&gt; def foo(x, y):
... return x[1]-y[1]
&gt;&gt;&gt; heap = heapify(l, cmp=foo)
</code></pre>

Any suggestions ?

In Python, heapq.heapify doesn't take cmp or key functions as arguments like sorted does

Python

我使用的是python2.6。它在更高版本的python中可用吗？还有没有其他方法可以为非平凡类的对象列表维护优先级队列？我需要的是这样的东西>>> l = [ ['a', 3], ['b', 1] ]>>> def foo(x, y):...   return x[1]-y[1]>>> heap = heapify(l, cmp=foo)有什么建议吗？

问在Python语言中，heapq.heapify不像排序那样将cmp或键函数作为参数
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python语言中，heapq.heapify不像排序那样将cmp或键函数作为参数EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Python语言中，heapq.heapify不像排序那样将cmp或键函数作为参数
EN