Python实现Priority queues（优先队列）模拟功能运行异常问题咨询

核心问题点 #

• 判断条件不符合同优先级插末尾的要求：原代码使用element[0] <= self.elements[i][0]作为判断条件之一，会在遇到第一个优先级大于等于当前元素的位置就插入，导致同优先级的新元素被插到现有同优先级元素的前面，和需求完全相反。
• 未处理新元素优先级最高的场景：如果新元素优先级比队列中所有已有元素都高，循环全程不会触发insert逻辑，最终新元素会直接丢失，不会被加入队列。
• 多余的二级字段判断：原代码的判断逻辑额外加了element[1] <= self.elements[i][1]的条件，除非你明确需要同优先级下按照第二个字段排序，否则这个多余条件会导致插入逻辑不符合预期。

修正后的代码实现 #

class PriorityQueue:

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

    def add(self, element):
        """
        把元素插入到列表的正确位置
        示例：如果现有队列的优先级序列为：
            1, 1, 1, 1, 2, 2, 2, 3, 5
        新增优先级为5的元素后结果为：
            1, 1, 1, 1, 2, 2, 2, 3, 5, 5
                                插入位置^
        """
        # 找到第一个优先级大于当前元素的位置，插入到该位置前即可保证同优先级新元素在末尾
        for i in range(len(self.elements)):
            if element[0] < self.elements[i][0]:
                self.elements.insert(i, element)
                return
        # 所有元素优先级都小于等于当前元素，直接追加到队列末尾
        self.elements.append(element)

如果需要同优先级下按照第二个字段做二级排序，可以把循环内的判断条件修改为：

if element[0] < self.elements[i][0] or (element[0] == self.elements[i][0] and element[1] < self.elements[i][1]):

内容的提问来源于stack exchange，提问作者miayang1661