Heappop() non invariant

Question

Lorsque j'utilise heapq.heappop (queue), le premier élément de la liste est déplacé, mais la liste restante est modifiée. Comment puis-je empêcher cela? (Tuples de note contenant 'r' et 'o' ci-dessous)

Ceci est ma sortie de débogage:

Queue: PQ: [(1, 2, 'z'), (1, 3, 't'), (2, 4, 'r'), (2, 5, 'o'), (2, 6, 'f')]

File d'attente avant Pop: [(1, 2, 'z') , (1, 3, 't'), (2, 4, 'r'), (2, 5, 'o'), (2, 6, 'f')]

priority, counter, node = heapq.heappop(queue) 

article retourné : (1, 2, 'z') File d'attente après Pop: [(1, 3, 't'), (2, 5, 'o'), (2, 4, 'r'), (2, 6 , 'f')]

Le compteur est censé s'assurer que les ajouts antérieurs d'un noeud se rapprochent de la file d'attente [0].

Ma file d'attente après pop ne fait pas que pop pile [0], elle réarrange et met un tuple contenant 'o' avant le tuple contenant 'r'. Leur priorité est la même (2), mais leur compteur est respectivement de 5 et 4, donc ils sont réarrangés dans le mauvais ordre.

Inst heappop() suppose seulement de renvoyer heap [0] et de déplacer tout le reste dans la file d'attente? Comment puis-je empêcher ce réarrangement?

Answer 1

Ceci est le comportement normal attendu d'un tas. Il n'y a AUCUN ordre implicite entre les éléments arbitraires du tas: le seul invariant est que chaque nœud est inférieur à l'un ou l'autre de ses enfants. Une fois que votre élément (1,3,'t') est sauté, (2,4,'r') sera choisi comme nouvelle racine puisque c'est le moindre des deux enfants de la racine précédente; sa commande relative à (2,5,'o') n'est pas pertinente jusqu'à ce moment-là. En d'autres termes, la racine est l'élément ONLY pour lequel vous pouvez dire quelque chose sur sa valeur en fonction de son index dans le tas.

Si vous voulez une liste qui est dans un ordre complètement trié à tout moment, vous voulez le module bisect, pas heapq. La performance sera bien pire, bien sûr.