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

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

所以，把接口和实现分开考虑。

循环优先级队列的接口会让您认为该结构是一个循环队列。它有一个"highest"优先级的头，下一个稍微低一点，然后走到最后，下一个又是头。

您编写的方法需要那样做。

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

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

您将这些细节隐藏在您的界面下方——当您到达终点时，您只是将自己重置为开头——您的界面使它看起来是圆形的。

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

An efficient way to implement circular priority queue?

python

priority-queue

data-structures

circular-queue