Python实现优先级队列

Question

我想在不使用Queue模块的情况下创建一个优先级队列。我做了一个类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) 

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

Answer 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