1.下面是cookbook的原代码,利用heapq模块实现了一个优先级队列,每次pop函数优先级高的被删除并返回。
import heapq
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
使用方式:
>>> class Item:
... def __init__(self, name):
... self.name = name
... def __repr__(self):
... return 'Item({!r})'.format(self.name)
...
>>> q = PriorityQueue()
>>> q.push(Item('foo'), 1)
>>> q.push(Item('bar'), 5)
>>> q.push(Item('spam'), 4)
>>> q.push(Item('grok'), 1)
>>> q.pop()
Item('bar')
>>> q.pop()
Item('spam')
>>> q.pop()
Item('foo')
>>> q.pop()
Item('grok')
那么,问题来了,heappop()函数会优先删除第一个元素,然后才是删除最小的元素,按照上面的使用,应该优先删除foo,然后才是最小的bar吧?这段代码是从哪里将它进行排序了么?
下面是普通的例子:
In [1]: x = [(-1, 0, 'for'), (-5, 1, 'bar'), (-4, 2, 'spam'), (-1, 3, 'grok')]
In [2]: import heapq
In [3]: heapq.heappop(x)[-1]
Out[3]: 'for'
In [4]: heapq.heappop(x)[-1]
Out[4]: 'bar'
In [5]: heapq.heappop(x)[-1]
Out[5]: 'spam'
In [6]: heapq.heappop(x)[-1]
Out[6]: 'grok'
我的背景是自学 + google,基本功不扎实,还请赐教。
你的例子里缺了一步:
heapq.heapify(x)
书中的例子里每一步 heappush()
都会进行排序。
首先,多谢 @Yushneng 的不吝赐教,查了下heappush的源码,总结下大概实现了以下的几个步骤:
1.将newitem appen进 heap里(这里的heap貌似可以是个列表,下面copy部分代码做了个小的实践)。
2.调用了_siftdown()函数,下面有源码,将newitem和父item进行了比较(源码定义了parent是newitem的位置-1然后向右位移1位,还不太理解这步骤操作,但是最终是产生了一个二叉树的结构。),此步骤保证了第一个元素必然是最小的(要是我只能想到sorted(),汗颜!)
下面是copy了两个函数,做了个实践,再次感谢 @Yushneng 。(自学编程,对于二叉树这种数据结构也是不太理解,还需要在看看。)
# _*_ coding:utf-8 _*_
#堆排序算法实例,摘自heapq库的一个函数,被用在heappush()等函数。
import heapq
import random
def siftdown(heap, startpos, pos):
newitem = heap[pos]
# Follow the path to the root, moving parents down until finding a place
# newitem fits.
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if cmp_lt(newitem, parent):
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
def cmp_lt(x, y):
# Use __lt__ if available; otherwise, try __le__.
# In Py3.x, only __lt__ will be called.
return (x < y) if hasattr(x, '__lt__') else (not y <= x)
# x = [10,2,9,8,11,3,4,1,5,23]
#print(type(heapq.heapify(x)))
x = []
for _ in range(10):
i = random.randrange(100)
x.append(i)
siftdown(x, 0, len(x)-1)
print(x)