Python中的双优先级优先队列

Question

我在找一种优先队列，这种队列可以让我设置两个优先级。
我希望它先检查第一个优先级，然后再检查第二个优先级。
这里有一些代码

import Queue

class Job(object):
    def __init__(self, fpriority, spriority, description, iata , hops, cost):
        self.fpriority = fpriority
        self.spriority = spriority

q = Queue.PriorityQueue()

q.put(Job(2, 5, 'Mid-level job'))
q.put(Job(2, 20, 'Low-level job'))
q.put(Job(1, 20, 'Important job'))

现在我想要元素按照以下顺序排列

Important job
Mid_level job
Low_level job

我该如何用一个队列来创建这样的顺序呢？

Answer 1

对于 python3，可以这样实现一个具有两个优先级的优先队列：

from queue import PriorityQueue


class CustomPriorityQueueItem(object):
    def __init__(self, data, first_priority, second_priority):
        self.first_priority = first_priority
        self.second_priority = second_priority
        self.data = data

    def __lt__(self, other):
        if self.first_priority < other.first_priority:
            return True
        elif self.first_priority == other.first_priority:
            if self.second_priority < other.second_priority:
                return True
            else:
                return False
        else:
            return False

    def __eq__(self, other):
        if self.first_priority == other.first_priority and self.second_priority == other.second_priority:
            return True
        else:
            return False

    def __str__(self):
        return str(self.data)

    def __repr__(self):
        return self.data


class CustomData:
    def __init__(self, name, description):
        self.name = name
        self.description = description

    def __str__(self):
        return self.name + ": " + self.description


# test data

if __name__ == "__main__":

    q = PriorityQueue()

    obj_arr = [
        CustomData('name-1', 'description-1'),  # this should come 6th - (3, 2)
        CustomData('name-2', 'description-2'),  # this should come 5st - (3, 1)
        CustomData('name-3', 'description-3'),  # this should come 2nd - (1, 1)
        CustomData('name-4', 'description-4'),  # this should come 1th - (1, 2)
        CustomData('name-5', 'description-5'),  # this should come 3rd - (2, 1)
        CustomData('name-6', 'description-6')   # this should come 4th - (2, 2)
    ]

    priorities = [(3, 2), (3, 1), (1, 2), (1, 1), (2, 1), (2, 2)]

    itr = 0
    for i in range(len(obj_arr)):
        first_priority = i + 1
        second_priority = itr % 2
        q.put(CustomPriorityQueueItem(
            obj_arr[i], priorities[itr][0], priorities[itr][1]))
        itr += 1

    while not q.empty():
        data = q.get()
        print(str(data))

---

Output:
name-4: description-4
name-3: description-3
name-5: description-5
name-6: description-6
name-2: description-2
name-1: description-1

Answer 2

使用NPE的策略 - 把一个元组作为队列的优先级，这个元组是(fpriority, spriority)：

import Queue

class Job(object):
    def __init__(self, fpriority, spriority, description='blah', iata='foo' , hops='ample', cost='free pitchers'):
        self.fpriority = fpriority
        self.spriority = spriority
        self.description = description
    @property
    def priority(self):
        return (self.fpriority, self.spriority)
    def __str__(self):
        return self.description

q = Queue.PriorityQueue()

second = Job(2, 5, 'Mid-level job')
third = Job(2, 20, 'Low-level job')
first = Job(1, 20, 'Important job')

q.put((second.priority, second))
q.put((third.priority, third))
q.put((first.priority, first))

while q.unfinished_tasks:
    task = q.get()
    print task, task[1]
    q.task_done()
>>> 
((1, 20), <__main__.Job object at 0x02A8F270>) Important job
((2, 5), <__main__.Job object at 0x02A8F230>) Mid-level job
((2, 20), <__main__.Job object at 0x02A8F250>) Low-level job
>>> 

这应该适用于任何数量的优先级元组中的项目。

>>> 
>>> t = [(1,2),(1,1),(2,2),(2,1),(1,3)]
>>> sorted(t)
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2)]
>>> t = [(2,2,67),(1,2,3),(1,1,0),(2,2,1),(2,1,78),(1,3,78),(1,2,2),(1,2,1),(1,1,6),(2,1,32)]
>>> sorted(t)
[(1, 1, 0), (1, 1, 6), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 78), (2, 1, 32), (2, 1, 78), (2, 2, 1), (2, 2, 67)]
>>>

Answer 3

只需把 (fpriority, spriority) 这个元组当作优先级来用就行了。这样就能按照你想要的方式进行排序（先比较第一个值，如果相同再比较第二个值来决定顺序）。

Answer 4

在编程中，有时候我们会遇到一些问题，特别是在使用某些工具或库的时候。这些问题可能会让我们感到困惑，不知道该如何解决。比如，有人可能在使用某个特定的功能时，发现它并没有按照预期的方式工作。这时候，我们就需要去查找相关的信息，看看有没有其他人遇到过类似的问题，以及他们是如何解决的。

在这个过程中，StackOverflow是一个非常有用的平台。它是一个问答网站，专门为程序员提供帮助。在这里，用户可以提出问题，也可以回答别人的问题。通过查看这些问答，我们可以获得很多实用的建议和解决方案。

总之，当你在编程时遇到困难，不妨去看看StackOverflow，那里可能会有你需要的答案。

class Job(object):
    def __init__(self, fpriority, spriority, description, iata , hops, cost):
        self.fpriority = fpriority
        self.spriority = spriority

    def __cmp__(self, other):
        '''Comparisons for Python 2.x - it's done differently in 3.x'''
        if self.fpriority > other.fpriority:
            return 1
        elif self.fpriority < other.fpriority:
            return -1
        else:
            if self.spriority > other.spriority:
                return 1
            elif self.spriority < other.spriority:
                return -1
            else:
                return 0