Qu'est-ce que le module heapq de Python?
j'ai essayé "heapq" et est arrivé à la conclusion que mes attentes diffèrent de ce que je vois sur l'écran. J'ai besoin que quelqu'un m'explique comment ça marche et où ça peut être utile.
dans le livre Module Python de la semaine sous le paragraphe 2.2 Tri il est écrit
Si vous avez besoin de maintenir une liste triée comme vous ajouter et supprimer des valeurs, découvrez heapq. En utilisant les fonctions dans heapq pour ajouter ou supprimer des éléments d'une liste, vous pouvez maintenir l'ordre de tri de la liste avec une faible surcharge.
voici ce que je fais et obtiens.
import heapq
heap = []
for i in range(10):
heap.append(i)
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
heapq.heapify(heap)
heapq.heappush(heap, 10)
heap
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
heapq.heappop(heap)
0
heap
[1, 3, 2, 7, 4, 5, 6, 10, 8, 9] <<< Why the list does not remain sorted?
heapq.heappushpop(heap, 11)
1
heap
[2, 3, 5, 7, 4, 11, 6, 10, 8, 9] <<< Why is 11 put between 4 and 6?
donc, comme vous voyez la liste "tas" n'est pas triée du tout, en fait plus vous ajoutez et supprimez les éléments plus encombré il devient. Les valeurs poussées prennent des positions inexplicables. Ce qui se passe?
3 réponses
heapq le module maintient le tas invariant, ce qui n'est pas la même chose que de maintenir l'objet liste actuel dans l'ordre.
citant le heapq documentation:
Tas sont des arbres binaires pour lesquels chaque nœud parent a une valeur inférieure ou égale à l'un de ses enfants. Cette implémentation utilise des tableaux pour
heap[k] <= heap[2*k+1]etheap[k] <= heap[2*k+2]pour toutk, en comptant les éléments à partir de zéro. Pour l' à titre de comparaison, les éléments non existants sont considérés comme infinis. La propriété intéressante d'un segment est que son plus petit élément est toujours la racine,heap[0].
Cela signifie qu'il est très efficace pour trouver le plus petit élément (il suffit de prendre heap[0]), ce qui est idéal pour une file d'attente prioritaire. Après cela, les 2 valeurs sera plus grande (ou égal) que le 1er, et 4 après qui vont être plus grandes que leurs "parents" nœud, puis les 8 prochains sont plus grandes, etc.
vous pouvez en savoir plus sur la théorie derrière l'infrastructure de données dans le section théorie de la documentation. Vous pouvez aussi regarder les cette conférence du MIT OpenCourseWare Introduction aux Algorithmes du cours, ce qui explique l'algorithme en termes généraux.
un tas peut être retourné très efficacement dans une liste triée:
def heapsort(heap):
return [heapq.heappop(heap) for _ in range(len(heap))]
en enlevant simplement l'élément suivant du tas. En utilisant sorted(heap) devrait être plus rapide néanmoins, comme le TimSort tirera profit de l'ordre partiel déjà présent dans un tas.
vous utiliseriez un tas si vous êtes seulement intéressé par la plus petite valeur, ou la première n les plus petites valeurs, particulièrement si vous êtes intéressé par ces valeurs sur une base continue; ajouter de nouveaux articles et supprimer les plus petites est en effet très efficace, plus que le recours à la liste chaque fois que vous avez ajouté une valeur.
Votre livre est faux! comme vous le démontrez, un tas n'est pas une liste triée (bien qu'une liste triée soit un tas). Qu'est ce qu'un tas de? Pour citer le manuel de conception D'algorithme de Skiena
Les tas sont une structure de données simple et élégante pour supporter efficacement les opérations de la file d'attente prioritaire insert et extract-min. Ils travaillent en maintenant un ordre partiel sur l'ensemble des éléments qui est plus faible que l'ordre trié (de sorte qu'il peut être efficace de maintenir) mais plus fort que ordre aléatoire (de sorte que l'élément minimum peut être rapidement identifié).
comparé à une liste triée, un tas obéit à une condition plus faible l'invariant de tas. Avant de le définir, pensez d'abord pourquoi relaxer la condition pourrait être utile. La réponse est que la condition la plus faible est plus facile à maintenir. Vous pouvez faire moins avec un tas, mais vous pouvez le faire plus vite.
Un tas a trois opérations:
- Rechercher-Minimum is O (1)
- Insérer O(log n)
- Remove-Min O (log n)
il est crucial D'insérer O(log n) Qui bat O (n) pour une liste triée.
Qu'est-ce que l'invariant de tas? "Un arbre binaire où les parents dominent leurs enfants". Qui est, "p ≤ c pour tous les enfants c de p". Skiena illustre avec des images et poursuit en démontrant l'algorithme pour insérer des éléments tout en maintenant l'invariant. Si vous réfléchissez un peu, vous pouvez les inventer vous-même. (Indice: ils sont connus comme bulle et bulle en bas)
la bonne nouvelle est que Python inclus dans les batteries implémente tout pour vous, dans le heapq module. Il ne définit pas un type tas (qui je pense serait plus facile à utiliser), mais les fournit comme fonctions d'aide sur la liste.
Moral:si vous écrivez un algorithme en utilisant une liste triée mais seulement jamais inspecter et supprimer d'une extrémité, alors vous pouvez rendre l'algorithme plus efficace en utilisant un tas.
Pour un problème dans lequel un tas de structure de données est utile, lire https://projecteuler.net/problem=500
il y a un malentendu au sujet de la mise en oeuvre de la structure de données du tas. heapq module est en fait une variante du tas binaire mise en œuvre, où des tas d'éléments sont stockés dans une liste, comme décrit ici: https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation
Citant Wikipedia:
les tas sont généralement implémentés avec un tableau. Tout arbre binaire peut être stocké dans un tableau, mais parce qu'un tas binaire est toujours un arbre binaire complet, il peut être stockés de manière compacte. Aucun espace n'est requis pour les pointeurs; au lieu de cela, le parent et les enfants de chaque noeud peuvent être trouvés par arithmétique sur les indices de tableau.
cette image ci-dessous devrait vous aider à sentir la différence entre la représentation de l'arbre et de la liste du tas et ( notez que c'est un tas max, qui est l'inverse du tas min habituel!):
en général, données tas la structure est différente d'une liste triée en ce qu'elle sacrifie certaines informations sur le fait de savoir si un élément particulier est plus grand ou plus petit que n'importe quel autre. Heap sait seulement, que cet élément particulier est moins, qu'il est parent et plus grand, qu'il est enfant. Moins une structure de données stocke d'informations, Moins il faut de temps/mémoire pour la modifier. Comparer la complexité de certaines opérations entre un segment et un tableau trié:
Heap Sorted array
Average Worst case Average Worst case
Space O(n) O(n) O(n) O(n)
Search O(n) O(n) O(log n) O(log n)
Insert O(1) O(log n) O(n) O(n)
Delete O(log n) O(log n) O(n) O(n)