pythonheapq有序队列

python库 heapq算法
本例是heapq的简易用法， heapq默认建立了小根堆

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')


本例中展示了heapq有序队列使用自定义类对象时的操作. 注意自定义类实现__cmp__即可. 注意__cmp__的符号顺序

• __cmp__比较为小于号时, 建立大根堆
• __cmp__比较为大于号时, 建立小根堆

import heapq
class MyObj:
def __init__(self, x, y):
self.x = x
self.y = y
def __cmp__(self, other):
return (self.x*10+self.y) > (other.x*10+other.y)
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
q = []
heapq.heapify(q) # 列表为空时不用这么做

# push操作
heapq.heappush(q, MyObj(4, 3))
heapq.heappush(q, MyObj(1, 2))
heapq.heappush(q, MyObj(2, 1))
while q:
# peek操作, 列表头就是堆顶
print(q[0].x, q[0].y)
# pop操作
next_item = heapq.heappop(q)
print(next_item.x, next_item.y)