Python et le tas intégré

Question

Pour le moment, j'essaye d'écrire une file d'attente prioritaire en Python en utilisant la bibliothèque intégrée heapq. Cependant, je suis bloqué en essayant de comprendre ce que Python fait avec le tie-break, je veux avoir une condition spécifique où je peux dicter ce qui se passe avec le tie-break au lieu de la bibliothèque heapq qui semble presque arracher quelque chose la file d'attente au hasard. Quelqu'un connaît-il un moyen de réécrire la condition de départage ou serait-il plus facile de construire la file d'attente prioritaire à partir de zéro?

Answer 1

heapq utilise les comparaisons intrinsèques sur les éléments de la file d'attente (__le__ et amis). La manière générale de contourner cette limite est la bonne vieille méthode connue sous le nom de «décorer/décorer» - c'est ce que nous faisions auparavant dans le tri, avant que le paramètre key= ne soit introduit ici. Pour le dire simplement, vous mettez en file d'attente et dequeue, non seulement les éléments qui vous intéressent ("charge utile"), mais plutôt les éléments "décorés" en tuples qui commencent par les "clés" dont vous avez besoin. Ainsi, par exemple, il serait normal de mettre en file d'attente un tuple comme (foo.x, time.time(), foo) si vous voulez prioriser par l'attribut x avec des liens cassés par le temps d'insertion dans la file d'attente - bien sûr lorsque vous vous désemparer de "décorer", en prenant le [-1] l'item du tuple que vous obtenez en dé-queuing. Alors, mettez les "clés secondaires" dont vous avez besoin pour être considérées comme "tie-break" dans le tuple "décoré" que vous mettez en file d'attente, APRÈS celles dont vous voulez rompre les "liens".