0

我正在尝试在不使用队列模块的情况下创建优先级队列。我已经创建了一个类 PriorityQueue() 并且我正在尝试创建一个不带参数并返回一个空队列但似乎无法弄清楚如何的 mk 函数。我的任务功能在这里：

class Task():

    __slots__ = ('name', priority)

def mkTask(myName, myPriority):
    t = Task()
    t.name = myName
    t.priority = myPriority
    return t

到目前为止，我的 PriorityQueue 类和检查队列是否为空的函数是这样的：

class PriorityQueue():
    def __init__(queue):
        queue.length = 0
        queue.first = None
        queue.last = None

def is_empty(queue):
    return(queue.length == 0)

我似乎无法弄清楚如何创建队列实例并将特定任务的元素插入队列。

4

1 回答 1

1

优先级队列通常使用堆来实现，这里有一个这样的实现。请注意，Python 中的堆实现返回堆中最小的东西，所以我否定优先级，以便首先弹出优先级最高的东西。

import heapq

class PriorityQueue:
    def __init__(self):
        self.items = []

    def push(self, priority, x):
        heapq.heappush(self.items, (-priority, x))

    def pop(self):
        _, x = heapq.heappop(self.items)
        return x

    def empty(self):
        return not self.items
于 2013-11-02T18:24:05.877 回答