Heapq с обычным предикатом сравнения

Я пытаюсь создать кучу с помощью специального предиката сортировки. Поскольку значения, входящие в него, имеют тип, определяемый пользователем, я не могу изменить свой встроенный предикат сравнения.

Есть ли способ сделать что-то вроде:

h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)

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

Ответы

Ответ 1

Согласно документации 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]

Ответ 2

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

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

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

Ответ 3

Ограничение с обоими ответами заключается в том, что они не позволяют связывать отношения как связи. Во-первых, связи нарушаются путем сравнения элементов, во втором - путем сравнения порядка ввода. Быстрее просто связывать связи, и если их много, это может иметь большое значение. Исходя из вышесказанного и в документах, неясно, можно ли это сделать в heapq. Кажется странным, что heapq не принимает ключ, а функции, полученные из него в том же модуле, -. P.S.: Если вы переходите по ссылке в первом комментарии ( "возможный дубликат..." ), есть еще одно предложение определения слова, которое похоже на решение.