在 Python 中使用堆创建优先级队列

Question

我是 Python 的新手，所以请原谅我犯的愚蠢错误... 我正在尝试在 python(2.7.15) 中使用堆创建优先级队列，但我的代码显然不起作用。

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
count = 0     # unique sequence count

def push(pq,task,priority=0):
    'Add a new task'
    count = count+1
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def update(pq,task, priority=0):
    'Add a new task or update the priority of an existing task'
    if task in entry_finder:
        remove_task(task)
    count = count+1
    entry = [priority, count, task]
    entry_finder[task] = entry
    heappush(pq, entry)

def remove_task(task):
    'Mark an existing task as REMOVED.  Raise KeyError if not found.'
    entry = entry_finder.pop(task)
    entry[-1] = REMOVED

def pop(pq):
    'Remove and return the lowest priority task. Raise KeyError if empty.'
    while pq:
        priority, count, task = heappop(pq)
        if task is not REMOVED:
            del entry_finder[task]
            return task
    raise KeyError('pop from an empty priority queue')

def IsEmpty(pq):
    if not pq:
    print("List is empty")

这就是我所做的，其中大部分被这里：https://docs.python.org/2/library/heapq.html。我的问题是当我尝试在 python 解释器上运行它时，我得到这个：

>>> pq=[]
>>> pq.push("task1",1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object has no attribute 'push'

我的问题是我该怎么做才能避免这个错误，如果我的代码有任何缺陷可能会导致更多错误？

Answer 1

您正在以 "object oriented C" 风格构建一个 class，涉及将对象上下文传递到函数中，例如do_something(instance, arg)。这是可能的，但对 Python 来说并不自然，它支持 classes 和一个名为 self 的关键字，它代表一个对象的实例，允许编写 instance.do_something(arg)就像您调用 push 函数时所做的那样。

使用这种方法，class 将封装您当前在全局范围内的所有状态数据：

pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
REMOVED = '<removed-task>'      # placeholder for a removed task
count = 0                       # unique sequence count

即使以 "C" 风格编写，程序也没有这些全局变量之外的实例状态；您需要某种结构来将这些变量放在一起并将它们传递给函数，或者对每个函数内的每个变量使用 global 关键字，这在状态安全方面不是一个很好的解决方案，可重用性、可理解性或任何其他设计指标。

这里有一个重构为 class 的程序示例：

from heapq import heappush, heappop


class PQ:
    def __init__(self):
        self.pq = []
        self.entry_finder = {}
        self.REMOVED = '<removed-task>'
        self.count = 0

    def push(self, task, priority=0):
        '''Add a new task
        '''
        self.count += 1
        entry = [priority, self.count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def update(self, task, priority=0):
        '''Add a new task or update the priority of an existing task
        '''
        if task in self.entry_finder:
            self.remove_task(task)

        self.count += 1
        entry = [priority, self.count, task]
        self.entry_finder[task] = entry
        heappush(self.pq, entry)

    def remove_task(self, task):
        '''Mark an existing task as REMOVED.  Raise KeyError if not found.
        '''
        entry = self.entry_finder.pop(task)
        entry[-1] = self.REMOVED

    def pop(self):
        '''Remove and return the lowest priority task. Raise KeyError if empty.
        '''
        while self.pq:
            priority, count, task = heappop(self.pq)

            if task is not self.REMOVED:
                del self.entry_finder[task]
                return task

        raise KeyError('pop from an empty priority queue')

    def empty(self):
        return len(self.pq) == 0

完成此操作后，您现在可以在解释器中导入 class（确保源代码在同一文件夹中，pq.py），创建 [=44= 的实例] 并开始使用它：

>>> from pq import PQ
>>> pq = PQ()
>>> pq.push(1, 20)
>>> pq.push(2, 30)
>>> pq.push(3, 10)
>>> while not pq.empty(): print pq.pop()
...
3
1
2
>>>

另一种常见做法是使用 if __name__ == '__main__': 条件将测试直接添加到 class 文件中：

if __name__ == '__main__':
    pq = PQ()
    pq.push(1, 20)
    pq.push(2, 30)
    pq.push(3, 10)

    while not pq.empty():
        print pq.pop()

这可以是运行在终端上 python pq.py。

Try it!

Answer 2

您定义push函数的方式，您需要将表示队列的列表作为第一个参数传递：

而不是

pq = []
pq.push("task1", 1)

做

pq = []
push(pq, "task1", 1)

在 Python 中使用堆创建优先级队列

Creating a priority queue using a heap in Python

heap

priority-queue

python-2.7