Obtener Max Heap en Python

1. Obtener Max Heap con números en Python
2. Obtener Max Heap con tuplas en Python
3. Referencias

El montón es la estructura de datos elegida para implementar una cola de prioridad. A diferencia de un árbol de búsqueda binaria, un montón no está completamente ordenado; no hay un orden definido entre hermanos o primos.

En Python, el módulo heapq implementa el algoritmo de cola del montón. Sin embargo, heapq solo proporciona la implementación Min Heap, en la que el valor de cualquier nodo padre es menor o igual que cualquiera de los valores de sus hijos.

La función principal, heappop(), devuelve el elemento más pequeño del montón.

Este artículo discutirá la implementación del comportamiento Max Heap en Python al combinar heapq con algún código personalizado.

Obtener Max Heap con números en Python

La estrategia más común cuando se trata de números es multiplicar los elementos de la lista por -1. Las funciones heapq pueden encargarse del montón.

Después de obtener el valor más pequeño, debemos volver a multiplicar la salida por -1 para obtener el valor máximo.

Código de ejemplo:

# 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)

Producción :

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

Obtener Max Heap con tuplas en Python

Es posible que deseemos implementar una cola de prioridad con tuplas en lugar de solo números. Dado que las tuplas de Python son inmutables, esto es un desafío para la tarea de multiplicar el número de prioridad por -1.

La solución radica en convertir primero cada tupla en una lista, modificando el primer elemento de estas sublistas por -1, volviéndolas a convertir en tuplas y, simultáneamente, creando una nueva lista con estas tuplas. Luego, la nueva lista se convierte en un montón usando heapify().

Para obtener el valor máximo, usamos heappop() en el montón, convertimos la tupla en una lista, modificamos el primer elemento para obtener un valor positivo y luego convertimos la lista nuevamente en una tupla.

Código de ejemplo:

# 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)

Producción :

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')

Se pueden implementar otras funciones de montón necesarias utilizando las mismas técnicas.

Referencias

Consulte la documentación del módulo heapq de Python para obtener más detalles y ejemplos.

El equipo de desarrollo de Python ha decidido no implementar funciones de almacenamiento dinámico máximo. Puede leer la solicitud de función y la respuesta aquí.