python 优先级队列实现

Question

我在使用以下参数创建插入函数时遇到问题。插入函数应该接受优先级队列和一个元素，并使用优先级规则插入它 -

优先级队列将接受一系列任务并对其进行排序基于它们的重要性。每个任务都有一个从 10（最高优先级）到 1 的整数优先级（最低优先级）。如果两个任务具有相同的优先级，则应根据顺序进行排序它们入到优先级队列中（之前先）。

因此，到目前为止，我已经创建了以下代码来初始化所需的一些内容......

class Tasks():
    __slots__ = ('name', 'priority')
     def __init__(bval):
         bval.name = myName
         bval.priority = myPriority
         return bval
class PriorityQueue():
    __slots__ = ('queue', 'element')
     def __init__(aval):
         aval.queue = queue
         aval.element = element
         return aval

我尝试编写的代码是insert（element，queue）：它应该使用优先级队列插入元素。同样，myPriorty 是一个介于 1 到 10 之间的整数。

同样，我可以执行以下操作以确保我创建从 1 到 10 的优先级......

def __init__(bval , myPriority = 10):
      bval.priority = myPriority
      bval.pq = [[] for priority in range(bval.myPriority)]

这样我就可以用 bval.pq 替换插入任务中的 myPriority

Answer 1

你为什么要重新发明轮子？

从队列导入优先级队列

http://docs.python.org/2/library/queue.html?highlight=priorityqueue#Queue.PriorityQueue

首先检索最低值的

条目（最低值的条目是由sorted（list（entryries））[0]返回的条目）。条目的典型模式是以下形式的元组：

（priority_number，数据）。

我使用这样的模块在 UI 和后台轮询线程之间进行通信。

READ_LOOP = 5
LOW_PRI = 3
MED_PRI = 2
HI_PRI = 1
X_HI_PRI = 0

然后像这样：

CoreGUI.TX_queue.put((X_HI_PRI,'STOP',[]))

Answer 2

请注意，有一个队列。如果您同意同步它，我会使用它。

否则，应使用堆来维护队列。请参阅 Python 文档及其示例。

Answer 3

摘自Alessandro Molina的一本好书"Modern Python Standard Library Cookbook"

堆是所有具有优先级的东西的完美匹配，例如 优先级队列：

import time
import heapq
class PriorityQueue:
    def __init__(self):
        self._q = []
    def add(self, value, priority=0):
        heapq.heappush(self._q, (priority, time.time(), value))
    def pop(self):
        return heapq.heappop(self._q)[-1]

例：

>>> def f1(): print('hello')
>>> def f2(): print('world')
>>>
>>> pq = PriorityQueue()
>>> pq.add(f2, priority=1)
>>> pq.add(f1, priority=0)
>>> pq.pop()()
hello
>>> pq.pop()()
world

Answer 4

deque（from collections import deque）是单个队列的python实现。您可以将项目添加到一端，并从另一端删除它们。如果每个优先级都有指定，则可以添加到所需的优先级。

在一起，它看起来有点像这样：

from collections import deque
class PriorityQueue:
    def __init__(self, priorities=10):
        self.subqueues = [deque() for _ in range(levels)]
    def enqueue(self, priorty, value):
        self.subqueues[priority].append(value)
    def dequeue(self):
        for queue in self.subqueues:
            try:
                return queue.popleft()
            except IndexError:
                continue