Очередь приоритетов с двумя значениями приоритетов

Question

Как хорошо известно, элементы, которые вставляются в приоритетную очередь, имеют значение, определяющее его приоритет. Например, если у меня есть пять элементов A,B,C,D,E с приоритетами (давайте назовем это значения приоритета priorityI):A = 10, B = 5, C = 1, D = 3, E = 2, Но как я могу написать очередь приоритетов, где я могу определить два значения приоритета, я имею в виду: если два элемента имеют одинаковое значение priorityIтогда значение priorityII решает, какой элемент следует взять первым, например:

element A has priorityI = 3, and prioriotyII = 5
element B has priorityI = 3, and prioriotyII = 1

тогда первый элемент B будет сначала взят из очереди.

Answer 1

Начиная с Python2.6, вы можете использовать Queue.PriorityQueue.

Элементы, вставленные в очередь, сортируются по __cmp__ метод, так что просто реализуйте один для класса, чьи объекты должны быть вставлены в очередь.

Обратите внимание, что если ваши элементы состоят из кортежей объектов, вам не нужно реализовывать контейнерный класс для кортежа, так как встроенная реализация сравнения кортежей, вероятно, соответствует вашим потребностям, как указано выше (сначала вставьте элемент с более низким значением). Тем не менее, вам может понадобиться реализовать __cmp__ метод для класса, чьи объекты находятся в кортеже.

>>> from Queue import PriorityQueue
>>> priority_queue = PriorityQueue()
>>> priority_queue.put((1, 2))
>>> priority_queue.put((1, 1))
>>> priority_queue.get()
(1, 1)
>>> priority_queue.get()
(1, 2)

РЕДАКТИРОВАТЬ: Как отметил @Blckknght, если ваша очередь приоритетов будет использоваться только одним потоком, модуль heapq, доступный из Python2.3, является предпочтительным решением. Если это так, пожалуйста, обратитесь к его ответу.

Answer 2

Обычный способ сделать это - сделать ваше значение приоритета кортежем двух ваших приоритетов. Python сортирует кортежи лексографически, поэтому сначала он сравнивает первый элемент кортежа каждого приоритета, и только при равенстве будут сравниваться следующие элементы.

Обычный способ создать приоритетную очередь в Python - это использовать heapqФункции модуля для управления списком. Поскольку все значение сравнивается, мы можем просто поместить два наших приоритета вместе со значением в один кортеж:

import heapq

q = []  # the queue is a regular list

A = (3, 5, "Element A")  # our first item, a three-tuple with two priorities and a value
B = (3, 1, "Element B")  # a second item

heapq.heappush(q, A)  # push the items into the queue
heapq.heappush(q, B)

print(heapq.heappop(q)[2])  # pop the highest priority item and print its value

Это печатает "Element B",