Python用最后添加的元素对队列进行排序

Question

实际上，我的排序算法是有效的，但是有一个问题。 我有一个类叫做SortedItem，它包括

def __init__(self, point, cost):
    self.coordinate = point
    self.cost = cost

我还有一个优先级队列，它根据成本对这个SortedItem进行排序：

^{pr2}$

问题出现在这里： -我定义了一些添加队列的顺序。假设我要将此对象添加到队列中：

obj1 = SortedItem((1,0), 10))
queue.enqueue(obj1)
obj2 = SortedItem((2,0), 15))
queue.enqueue(obj2)
obj3 = SortedItem((2,1), 15))
queue.enqueue(obj3)

• 现在我必须按如下顺序从队列中获取对象（obj1、obj2、obj3）。在
• 但是python内置的sort函数对这些对象进行如下排序：（obj1、obj3、obj2）（因为obj2和obj3的成本相同）
• 我怎样才能解决这个问题。我的意思是如果两个物体的成本是一样的，我应该得到第一个添加的。在

请注意：我刚刚创建了一个简单的问题示例。如果您尝试此代码，您可以按以下顺序获取对象：obj1、obj2、obj3

Answer 1

而不是按相反的顺序把它们从右边移走

def enqueue(self, item):
    self.items.append(item)
    self.items.sort(key=self.sortComparatorByCost, reverse=True)

def dequeue(self):
    return self.items.pop()

你可以把它们从左边移走。这将避免以相同的成本颠倒项目的插入顺序。在

def enqueue(self, item):
    self.items.append(item)
    self.items.sort(key=self.sortComparatorByCost)

def dequeue(self):
    return self.items.pop(0)

但是，从列表is not efficient开始删除项，这样您可以更好地使用^{}（将pop(0)替换为popleft()）来解决这个问题。另一方面，deque没有到位的sort()方法，因此也需要将self.items.sort()替换为self.items = deque(sorted(self.items))。在