Python Priority Queue Le mystère du résultat de la fonction heapify qui ne intéresserait pas la plupart des gens

introduction

J'ai étudié la partie mystérieuse du comportement de la file d'attente prioritaire en Python.

Comportement mystérieux

Ici , lorsque je vérifiais la file de priorité en Python, il était possible de le réaliser avec la librairie heapq. .. Dans le lien ci-dessus, ce qui suit est décrit comme un exemple d'utilisation de heapq.

#Source: https://qiita.com/ell/items/fe52a9eb9499b7060ed6
import heapq  #importation de la bibliothèque heapq

a = [1, 6, 8, 0, -1]
heapq.heapify(a)  #Liste de la file d'attente prioritaire
print(a)
#production: [-1, 0, 8, 1, 6](File d'attente prioritaire a)

Pourquoi la sortie est-elle dans cette séquence ([-1, 0, 8, 1, 6])? Une question s'est posée qui ne semblait intéresser personne (car je m'attendais à un ordre croissant).

Raison: parce que les éléments de la liste sont triés par l'algorithme de file d'attente du tas

En Python, il semble que les files d'attente prioritaires soient représentées par une liste, Selon le document python , l'algorithme de file d'attente du tas trie le contenu de la liste. chose.

Ici Le site d'explication du tas a une explication détaillée de l'algorithme du tas. , L'arborescence peut être représentée par une liste (en supposant que l'index de liste du nœud parent est i, le nœud gauche de l'enfant est 2 * i et le nœud droit est 2 * i + 1). La sortie ci-dessus a été obtenue en échangeant les éléments dans la liste afin que la relation parent-enfant soit établie.

Trier le flux par algorithme de file d'attente de tas

• Voir ici pour l'algorithme détaillé.

Condition du tas: chaque nœud est inférieur ou égal à ses nœuds enfants Séquence initiale: [1, 6, 8, 0, -1]