Python - Montones

Heap es una estructura de árbol especial en la que cada nodo padre es menor o igual que su nodo hijo. Entonces se llama Min Heap. Si cada nodo padre es mayor o igual que su nodo hijo, se denomina montón máximo. Es muy útil implementar colas de prioridad donde el elemento de la cola con mayor peso tiene más prioridad en el procesamiento. Una discusión detallada sobre montones está disponible en nuestro sitio web aquí. Estúdielo primero si es nuevo en la estructura de datos de la cabeza. En este capítulo veremos la implementación de la estructura de datos del montón usando Python.

Crear un montón

Se crea un montón utilizando la biblioteca incorporada de Python llamada heapq. Esta biblioteca tiene las funciones relevantes para realizar diversas operaciones en la estructura de datos del montón. A continuación se muestra una lista de estas funciones.

• heapify: esta función convierte una lista normal en un montón. En el montón resultante, el elemento más pequeño se coloca en la posición de índice 0. Pero el resto de los elementos de datos no están necesariamente ordenados.
• heappush: esta función agrega un elemento al montón sin alterar el montón actual.
• heappop: esta función devuelve el elemento de datos más pequeño del montón.
• heapreplace: esta función reemplaza el elemento de datos más pequeño con un nuevo valor proporcionado en la función.

Creando un montón

Un montón se crea simplemente usando una lista de elementos con la función heapify. En el siguiente ejemplo, proporcionamos una lista de elementos y la función heapify reorganiza los elementos llevando el elemento más pequeño a la primera posición.

import heapq

H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[1, 3, 5, 78, 21, 45]

Insertar en el montón

Insertar un elemento de datos en un montón siempre agrega el elemento en el último índice. Pero puede aplicar la función heapify nuevamente para traer el elemento recién agregado al primer índice solo si tiene el valor más pequeño. En el siguiente ejemplo, insertamos el número 8.

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

Eliminando del montón

Puede eliminar el elemento en el primer índice utilizando esta función. En el siguiente ejemplo, la función siempre eliminará el elemento en la posición de índice 1.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

Cuando se ejecuta el código anterior, produce el siguiente resultado:

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

Reemplazo en un montón

La función heapreplace siempre elimina el elemento más pequeño del montón e inserta el nuevo elemento entrante en algún lugar no fijado por ningún orden.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Replace an element
heapq.heapreplace(H,6)
print(H)

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]