heapq с пользовательским предикатом сравнения

Question

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

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

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

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

Answer 1

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

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

Класс ниже содержит внутренний список, гдекаждый элемент является кортежем, первый элемент которого является ключом, вычисляемым во время вставки элемента с использованием параметра key, передаваемого в экземпляре Heap:

# -*- 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]

Answer 2

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

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

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

Answer 3

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