heapq avec prédicat de comparaison personnalisé

Question

J'essaie de construire un tas avec un prédicat de tri personnalisé. Comme les valeurs qui y entrent sont de type "défini par l'utilisateur", je ne peux pas modifier leur prédicat de comparaison intégré.

Y a-t-il un moyen de faire quelque chose comme :

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

Ou encore mieux, je pourrais envelopper les fonctions heapq dans mon propre conteneur afin de ne pas avoir à passer le prédicat.

Answer 1

Selon le documentation sur l'heapq La façon de personnaliser l'ordre du tas est de faire en sorte que chaque élément du tas soit un tuple, le premier élément du tuple étant un élément qui accepte les comparaisons Python normales.

Les fonctions du module heapq sont un peu lourdes (puisqu'elles ne sont pas orientées objet), et nécessitent toujours que notre objet heap (une liste heapifiée) soit explicitement passé en premier paramètre. Nous pouvons faire d'une pierre deux coups en créant une classe wrapper très simple qui nous permettra de spécifier un objet key et présente le tas comme un objet.

La classe ci-dessous conserve une liste interne, où chaque élément est un tuple, dont le premier membre est une clé, calculée au moment de l'insertion de l'élément à l'aide de la fonction key passé lors de l'instanciation du tas :

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
   def __init__(self, initial=None, key=lambda x:x):
       self.key = key
       self.index = 0
       if initial:
           self._data = [(key(item), i, item) for i, item in enumerate(initial)]
           self.index = len(self._data)
           heapq.heapify(self._data)
       else:
           self._data = []

   def push(self, item):
       heapq.heappush(self._data, (self.key(item), self.index, item))
       self.index += 1

   def pop(self):
       return heapq.heappop(self._data)[2]

(Le supplément self.index est d'éviter les conflits lorsque la valeur de la clé évaluée est un tirage et que la valeur stockée n'est pas directement comparable - sinon heapq pourrait échouer avec TypeError)

Answer 2

Définissez une classe, dans laquelle vous surchargez la fonction __lt__() fonction. Voir l'exemple ci-dessous (fonctionne en Python 3.7) :

import heapq

class Node(object):
    def __init__(self, val: int):
        self.val = val

    def __repr__(self):
        return f'Node value: {self.val}'

    def __lt__(self, other):
        return self.val < other.val

heap = [Node(2), Node(0), Node(1), Node(4), Node(2)]
heapq.heapify(heap)
print(heap)  # output: [Node value: 0, Node value: 2, Node value: 1, Node value: 4, Node value: 2]

heapq.heappop(heap)
print(heap)  # output: [Node value: 1, Node value: 2, Node value: 2, Node value: 4]

Answer 3

En documentation sur l'heapq suggère que les éléments du tas pourraient être des tuples dans lesquels le premier élément est prioritaire et définit l'ordre de tri.

Cependant, ce qui est plus pertinent pour votre question, c'est que la documentation comprend une discussion avec un exemple de code de la façon dont on pourrait implémenter ses propres fonctions de wrapper heapq pour traiter les problèmes de stabilité de tri et d'éléments avec une priorité égale (parmi d'autres problèmes).

En bref, leur solution consiste à faire en sorte que chaque élément du heapq soit un triple avec la priorité, un nombre d'entrées et l'élément à insérer. Le nombre d'entrées garantit que les éléments ayant la même priorité sont triés dans l'ordre où ils ont été ajoutés au heapq.

Answer 4

setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

Utilisez ceci pour comparer les valeurs des objets dans heapq

Answer 5

La limite de ces deux réponses est qu'elles ne permettent pas de traiter les liens comme des liens. Dans la première, les égalités sont brisées en comparant les éléments, dans la seconde en comparant l'ordre d'entrée. Il est plus rapide de laisser les égalités être des égalités, et s'il y en a beaucoup, cela peut faire une grande différence. Sur la base de ce qui précède et de la documentation, il n'est pas clair si cela peut être réalisé dans heapq. Il semble étrange que heapq n'accepte pas de clé, alors que les fonctions qui en sont dérivées dans le même module l'acceptent.
P.S. : Si vous suivez le lien dans le premier commentaire ("possible duplicate...") il y a une autre suggestion de définir le qui semble être une solution.