Python 按队列中最后添加的元素排序

Question

实际上我的排序算法可以工作，但是有一个问题。我有一个名为 SortedItem 的类，其中包括

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

我还有优先级队列，它按成本对这个 SortedItem 进行排序:

class PriorityQueue:

def __init__(self):
    self.items = []

def isEmpty(self):
    return self.items == []

def sortComparatorByCost(self, item):
    return item.cost

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


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

def returnQueueAsString(self):
    queue_str = ""
    for eachItem in self.items:
        queue_str += str(eachItem) + " "
    return queue_str

def isQueueContainsElement(self, element):
    for eachElement in self.items:
        if eachElement[0] == element:
            return True
    return False

问题出现在这里:- 我已经定义了一些命令来添加队列。假设我要将此对象添加到队列中:

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 内置排序函数对这些对象进行排序，如下所示:(obj1, obj3, obj2)(因为 obj2 和 obj3 具有相同的成本)
• 我该如何解决这个问题。我的意思是如果 2 个对象的成本相同，我应该得到第一个添加的对象。

请注意:我刚刚为我的问题创建了一个简单示例。如果您尝试此代码，您可能会按以下顺序获得对象: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 , 但是，这样你可以更好地使用 deque (用 popleft() 替换 pop(0))来解决这个问题。另一方面，deque 没有就地 sort() 方法，因此需要替换 self.items.sort()通过 self.items = deque(sorted(self.items)) 也是如此。