Я пытаюсь создать кучу с помощью специального предиката сортировки. Поскольку значения, входящие в него, имеют тип, определяемый пользователем, я не могу изменить свой встроенный предикат сравнения.
Есть ли способ сделать что-то вроде:
h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)
Или даже лучше, я мог бы обернуть функции heapq в моем собственном контейнере, поэтому мне не нужно продолжать передавать предикат.
Согласно документации heapq, способ настройки порядка кучи состоит в том, чтобы каждый элемент в куче был кортежем, а первый элемент кортежа является тем, который принимает обычные сравнения Python.
Функции в модуле heapq являются немного громоздкими (поскольку они не являются объектно-ориентированными) и всегда требуют, чтобы наш объект кучи (heapified list) был явно передан в качестве первого параметра. Мы можем убить двух птиц одним камнем, создав очень простой класс-оболочку, который позволит нам указать функцию key и представить кучу в качестве объекта.
В приведенном ниже классе хранится внутренний список, где каждый элемент является кортежем, первый элемент которого является ключом, вычисленным во время ввода элемента с использованием параметра key, переданного при создании экземпляра кучи:
# -*- coding: utf-8 -*-
import heapq
class MyHeap(object):
def __init__(self, initial=None, key=lambda x:x):
self.key = key
if initial:
self._data = [(key(item), item) for item in initial]
heapq.heapify(self._data)
else:
self._data = []
def push(self, item):
heapq.heappush(self._data, (self.key(item), item))
def pop(self):
return heapq.heappop(self._data)[1]
документация heapq предполагает, что элементы кучи могут быть кортежами, в которых первый элемент является приоритетом и определяет порядок сортировки.
Более уместным для вашего вопроса является то, что документация включает в себя обсуждение с образцом кода о том, как можно реализовать собственные функции оболочки heapq для решения проблем стабильности сортировки и элементов с равным приоритетом (среди прочих вопросов).
Вкратце, их решение состоит в том, чтобы каждый элемент в heapq был тройкой с приоритетом, количеством записей и элементом, который нужно вставить. Счетчик записей гарантирует, что элементы с одинаковым приоритетом сортируются в том порядке, в котором они были добавлены в heapq.
Ограничение с обоими ответами заключается в том, что они не позволяют связывать отношения как связи. Во-первых, связи нарушаются путем сравнения элементов, во втором - путем сравнения порядка ввода. Быстрее просто связывать связи, и если их много, это может иметь большое значение. Исходя из вышесказанного и в документах, неясно, можно ли это сделать в heapq. Кажется странным, что heapq не принимает ключ, а функции, полученные из него в том же модуле, -. P.S.: Если вы переходите по ссылке в первом комментарии ( "возможный дубликат..." ), есть еще одно предложение определения слова, которое похоже на решение.