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