一种实现循环优先级队列的有效方法？

Question

我设计了一个循环优先级队列。但我花了一段时间，因为它是有条件的，并且有点时间复杂性

我使用一个列表实现了它。但我需要一个更高效的循环优先级队列实现

我将举例说明我的队列结构，有时它将有助于寻求代码的人理解循环优先级队列

class PriorityQueue:

    def __init__(self,n,key=None):
        if key is None:
            key=lambda x:x
        self.maxsize = n
        self.key=key
        self.arr = list(range(self.maxsize))
        self.rear = -1
        self.front = 0
        self.nelements=0

    def isPQueueful(self):
        return self.nelements==self.maxsize

    def isPQueueempty(self):
        return self.nelements==0

    def insert(self, item):

        if not self.isPQueueful():
            pos=self.rear+1
            scope = range(self.rear - self.maxsize, self.front - self.maxsize - 1, -1)
            if self.rear==0 and self.rear<self.front:
                scope=range(0,self.front-self.maxsize-1,-1)
            for i in scope:
                if self.key(item)>self.key(self.arr[i]):
                    self.arr[i+1]=self.arr[i]
                    pos=i
                else:
                    break
            self.rear+=1
            if self.rear==self.maxsize:
                self.rear=0
            if pos==self.maxsize:
                pos=0
            self.arr[pos]=item
            self.nelements+=1
        else:
            print("Priority Queue is full")

    def remove(self):

        revalue=None
        if not self.isPQueueempty():
            revalue=self.arr[self.front]
            self.front+=1
            if self.front==self.maxsize:
                self.front=0
            self.nelements-=1

        else:
            print("Priority Queue is empty")
        return revalue

如果有人能说出我所设计的是否适合用于生产代码，我将不胜感激。我认为这主要不是一个有效的方法

如果是这样，你能告诉我如何设计一个高效的循环优先级队列

Answer 1

因此，请分别考虑接口和实现

循环优先级队列的接口将使您认为该结构是一个循环队列。它有一个“最高”优先级的头部，下一个稍微低一点，然后你到达终点，下一个是头部

您编写的方法需要这样做

但是实现实际上不需要任何类型的队列、列表、数组或线性结构

对于实现，您试图维护一组始终按优先级排序的节点。因此，最好使用某种平衡树（例如红黑树）

你把细节隐藏在你的界面下面，当你到达终点时，你只需将自己重新设置到起点。你的界面使它看起来是圆形的