Comment est-ce que je peux heapifier un heapq dans O (lgn)?

Question

Possible en double:
How can I implement decrease-key functionality in Python's heapq?

Salut,

J'utilise heapq en Python pour mettre en œuvre une file d'attente prioritaire. Les éléments à l'intérieur de la file d'attente obtiennent beaucoup de changements de leurs priorités, et quand cela arrive, j'ai besoin de heapifier le tas. Le problème est que heapq a seulement une fonction heapify qui entasse le tas entier, plutôt que heapify qui commence à partir d'un certain élément dans le tas sachant que le reste est déjà un tas bien ordonné (comme le livre classique CS heapify) .
La différence est significative car chaque appel heapify est O (n) au lieu de O (lgn). Peut-il être fait sans implémenter un tas en utilisant une liste standard?

Merci!

---

Il semble que ma question est un double de How can I implement decrease-key functionality in Python's heapq?
La réponse, il indique qu'il n'y a pas moyen de contourner réimplémentant une file d'attente en fonction de tas avec bon O (LGN) heapify d'un élément spécifique.

Answer 1

J'ai été capable d'éviter ce problème avec heapify en invalidant l'élément de tas courant (lever un drapeau à l'intérieur de l'objet) et de pousser un objet identique sur le tas (qui est O (lgn)).
Cela peut gonfler le tas avec certains éléments invalides (que je nettoie à pop()), mais évite de réimplémenter le tas avec des objets tas sachant leur position de tas actuelle et une nouvelle position basée sur heapify.