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

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

heapq.png

Recommended Posts

Python Priority Queue Le mystère du résultat de la fonction heapify qui ne intéresserait pas la plupart des gens
Une fonction qui mesure le temps de traitement d'une méthode en python
Le résultat de l'installation de python sur Anaconda
Récupérer l'appelant d'une fonction en Python
Afficher le résultat du traitement de la géométrie en Python
Mesurons le résultat de l'exécution du programme avec C ++, Java, Python.
[Mémo] Le mystère des instructions d'affectation cumulative dans les fonctions Python
Le résultat de l'apprentissage automatique des ingénieurs Java avec Python www
traitement python3 qui semble utilisable dans paiza
Avoir le graphique d'équation de la fonction linéaire dessiné en Python
[Python] Réduisons le nombre d'éléments dans le résultat dans le fonctionnement de l'ensemble
Essayez de transcrire la fonction de masse stochastique de la distribution binomiale en Python
[Python] Un programme qui calcule le nombre de chaussettes jumelées
Je veux convertir par lots le résultat de "chaîne de caractères" .split () en Python
Fonction Eval () qui calcule une chaîne de caractères comme expression en python
[Python] Note: Fonction auto-conçue pour trouver la zone de distribution normale
Vérifiez le comportement du destroyer en Python
Prenez la somme logique de List en Python (fonction zip)
[Python3] Réécrire l'objet code de la fonction
Principes de base pour exécuter NoxPlayer en Python
À la recherche du FizzBuzz le plus rapide en Python
Comment passer le résultat de l'exécution d'une commande shell dans une liste en Python
Vous serez ingénieur dans 100 jours - Jour 29 - Python - Bases du langage Python 5
Vous serez ingénieur dans 100 jours - Jour 33 - Python - Bases du langage Python 8
Vous serez ingénieur dans 100 jours --Jour 26 --Python --Basiques du langage Python 3
Je souhaite créer une file d'attente prioritaire pouvant être mise à jour avec Python (2.7)
Définir la limite supérieure du nombre de répétitions de fonctions récursives en Python
Comment trouver le coefficient de la courbe approximative passant par les sommets en Python
Vous serez ingénieur dans 100 jours --Jour 32 --Python --Basiques du langage Python 7
Correspondance de l'événement selon lequel le résultat de form.is_valid () est toujours False dans le système Django2
Vous serez ingénieur dans 100 jours --Jour 28 --Python --Les bases du langage Python 4
[Python] J'ai examiné une pratique qui peut être exécutée en parallèle avec le thread principal par traitement asynchrone (multiprocessing, asyncio)