Combinar dos arrays ordenadas en Python usando heapq

Dadas dos arrays ordenadas, la tarea es fusionarlas de manera ordenada. Ejemplos:

Input :  arr1 = [1, 3, 4, 5]  
         arr2 = [2, 4, 6, 8]
Output : arr3 = [1, 2, 3, 4, 4, 5, 6, 8]

Input  : arr1 = [5, 8, 9]  
         arr2 = [4, 7, 8]
Output : arr3 = [4, 5, 7, 8, 8, 9]

Este problema tiene una solución existente, consulte el enlace Fusionar dos arrays ordenadas . Resolveremos este problema en python usando heapq.merge() en una sola línea de código. 

Implementación:

# Function to merge two sorted arrays
from heapq import merge
 
def mergeArray(arr1,arr2):
    return list(merge(arr1, arr2))
 
# Driver function
if __name__ == "__main__":
    arr1 = [1,3,4,5] 
    arr2 = [2,4,6,8]
    print (mergeArray(arr1, arr2))

[1, 2, 3, 4, 4, 5, 6, 8]

¿Propiedades del módulo heapq?

Este módulo proporciona una implementación del algoritmo de cola de almacenamiento dinámico, también conocido como algoritmo de cola de prioridad. Para crear un montón, use una lista inicializada en [], o puede transformar una lista poblada en un montón mediante la función heapify(). Se proporcionan las siguientes funciones:

• heapq.heappush(heap,item) : Inserte el elemento de valor en el montón, manteniendo el montón invariable.
• heapq.heappop(heap) : extrae y devuelve el elemento más pequeño del montón, manteniendo el montón invariable. Si el montón está vacío, se genera IndexError . Para acceder al elemento más pequeño sin abrirlo, use heap[0].
• heapq.heappushpop(heap, item) : empuja el elemento en el montón, luego extrae y devuelve el elemento más pequeño del montón. La acción combinada se ejecuta de manera más eficiente que heappush() seguida de una llamada separada a heappop().
• heapq.heapify(x) : transforma la lista x en un montón, en el lugar, en tiempo lineal.
• heapq.merge(*iterables): combine varias entradas ordenadas en una sola salida ordenada (por ejemplo, combine entradas con marca de tiempo de varios archivos de registro). Devuelve un iterador sobre los valores ordenados.