В Python heapq.heapify не принимает cmp или ключевые функции в качестве аргументов, как отсортировано

Я использую python2.6. Доступен ли он в более высокой версии python?
Else есть другой способ, которым я могу поддерживать очереди приоритетов для списка объектов нетривиальных классов? Мне нужно что-то вроде этого

>>> l = [ ['a', 3], ['b', 1] ]
>>> def foo(x, y):
...   return x[1]-y[1]
>>> heap = heapify(l, cmp=foo)

Любые предложения?

Ответ 1

Традиционным решением является сохранение (приоритет, задача) кортежей в куче:

pq = [ ]
heappush(pq, (10, task1))
heappush(pq, (5, task2))
heappush(pq, (15, task3))
priority, task = heappop(pq)

Это работает отлично, если две задачи не имеют одинакового приоритета; в противном случае сами задачи сравниваются (что может вообще не работать в Python 3).

В обычных документах дается руководство по реализации приоритетных очередей с использованием heapq:

http://docs.python.org/library/heapq.html#priority-queue-implementation-notes

Ответ 2

Просто напишите подходящий метод __lt__ для объектов в списке, чтобы они правильно отсортировались:

class FirstList(list):
    def __lt__(self, other):
        return self[0] < other[0]

lst = [ ['a', 3], ['b', 1] ]

lst = [FirstList(item) for item in lst]

Для сортировки Python требуется только __lt__, хотя рекомендуется определить все сравнения или использовать functools.total_ordering.

Вы можете видеть, что он работает, используя два элемента с тем же самым первым значением и разными вторыми значениями. Эти два объекта будут меняться местами, когда вы heapify независимо от того, что второе значение, потому что lst[0] < lst[1] всегда будет False. Если вам нужна стабильность heapify, вам потребуется более сложное сравнение.

Ответ 3

Ну, это ужасно и ужасно, и вы определенно не должны этого делать... Но похоже, что модуль heapq определяет функцию cmp_lt, который вы можете использовать для патча обезьяны, если вам действительно нужна пользовательская функция сравнения.

Ответ 4

Я не знаю, лучше ли это, но это похоже на решение Раймона Хеттингера, но приоритет определяется из объекта.

Пусть это будет вашим объектом, и вы хотите отсортировать его по атрибуту x.

class Item:                                 
    def __init__(self, x):
        self.x = x

Затем имеем функцию, которая применяет спаривание

def create_pairs(items):
     return map(lambda item: (item.x, item), items)

Затем примените функцию к спискам в качестве входа в heapq.merge

list(heapq.merge(create_pairs([Item(1), Item(3)]), 
                 create_pairs([Item(2), Item(5)])))

Который дал мне следующий вывод

[(1, <__main__.Item instance at 0x2660cb0>),
 (2, <__main__.Item instance at 0x26c2830>),
 (3, <__main__.Item instance at 0x26c27e8>),
 (5, <__main__.Item instance at 0x26c2878>)]