Obtenir Max Heap en Python

1. Obtenir Max Heap avec des nombres en Python
2. Obtenir Max Heap avec Tuples en Python
3. Références

Le tas est la structure de données de choix pour implémenter une file d’attente prioritaire. Contrairement à un arbre de recherche binaire, un tas n’est pas entièrement ordonné ; il n’y a pas d’ordre défini entre frères et sœurs ou cousins.

En Python, le module heapq implémente l’algorithme heap queue. Cependant, heapq ne fournit que l’implémentation Min Heap, dans laquelle la valeur de tout nœud parent est inférieure ou égale à l’une des valeurs de ses enfants.

La fonction principale, heappop(), renvoie le plus petit élément du tas.

Cet article discutera de la mise en œuvre du comportement Max Heap en Python en combinant heapq avec du code personnalisé.

Obtenir Max Heap avec des nombres en Python

La stratégie la plus courante lorsqu’il s’agit de nombres consiste à multiplier les éléments de la liste par -1. Les fonctions heapq peuvent s’occuper du tas.

Après avoir extrait la plus petite valeur, nous devons à nouveau multiplier la sortie par -1 pour obtenir la valeur maximale.

Exemple de code :

# import the heapq module.
import heapq

# Max Heap With Numbers

# Create a list.
x = [5, 4, 3, 6, 8, 7, 2, 1]
# Print the list.
print(x)

# Multiply elements by -1.
x_inv = [-1 * i for i in x]
print(x_inv)

# Make the heap.
heapq.heapify(x_inv)

# Pop the maximum value.
# RUN ONE LINE AT A TIME.
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)
-1 * heapq.heappop(x_inv)

Production:

print(x)
[5, 4, 3, 6, 8, 7, 2, 1]

print(x_inv)
[-5, -4, -3, -6, -8, -7, -2, -1]

-1 * heapq.heappop(x_inv)
Out[8]: 8

-1 * heapq.heappop(x_inv)
Out[9]: 7

-1 * heapq.heappop(x_inv)
Out[10]: 6

Obtenir Max Heap avec Tuples en Python

Nous pouvons souhaiter implémenter une file d’attente prioritaire avec des tuples plutôt que de simples nombres. Étant donné que les tuples de Python sont immuables, il s’agit d’un défi pour la tâche de multiplier le numéro de priorité par -1.

La solution consiste à convertir d’abord chaque tuple en une liste, à modifier le premier élément de ces sous-listes par -1, à les reconvertir en tuples et à créer simultanément une nouvelle liste avec ces tuples. La nouvelle liste est ensuite convertie en tas à l’aide de heapify().

Pour faire apparaître la valeur maximale, nous utilisons heappop() sur le tas, convertissons le tuple en liste, modifions le premier élément pour obtenir une valeur positive, puis reconvertissons la liste en tuple.

Exemple de code :

# Max Heap With Tuples

# Make a list of tuples.
l = [(1, "A"), (5, "B"), (3, "C"), (7, "D"), (6.5, "E")]
# View the list.
l

# Create an empty list to hold modified tuples.
l_max = []

# Populate the list with modified tuples.
for i in range(len(l)):
    j = list(l[i])
    j[0] = -1 * j[0]
    l_max.append(tuple(j))

# View the modified list.
l_max

# Create the min heap.
heapq.heapify(l_max)

# View the min-heap.
l_max

# Create a function that uses meappop and
# changes the number back to a positive value.


def maxpop(mh):
    l = list(heapq.heappop(mh))
    l[0] = -1 * l[0]
    return tuple(l)


# Test the values popped by the maxpop.
# RUN ONE LINE AT A TIME.
maxpop(l_max)
maxpop(l_max)
maxpop(l_max)

Production:

l
Out[15]: [(1, 'A'), (5, 'B'), (3, 'C'), (7, 'D'), (6.5, 'E')]

l_max
Out[14]: [(-1, 'A'), (-5, 'B'), (-3, 'C'), (-7, 'D'), (-6.5, 'E')]

heapq.heapify(l_max)

l_max
Out[17]: [(-7, 'D'), (-6.5, 'E'), (-3, 'C'), (-5, 'B'), (-1, 'A')]

maxpop(l_max)
Out[19]: (7, 'D')

maxpop(l_max)
Out[20]: (6.5, 'E')

maxpop(l_max)
Out[21]: (5, 'B')

D’autres fonctions de tas nécessaires peuvent être implémentées en utilisant les mêmes techniques.

Références

Voir la documentation du module heapq de Python pour plus de détails et d’exemples.

L’équipe de développement Python a décidé de ne pas implémenter les fonctions max heap. Vous pouvez lire la demande de fonctionnalité et la réponse ici.