Combine dos arrays ordenadas usando la cola de prioridad

Dadas dos arrays ordenadas A[] y B[] de tamaños N y M respectivamente, la tarea es fusionarlas de manera ordenada.

Ejemplos:

Entrada: A[] = { 5, 6, 8 }, B[] = { 4, 7, 8 }
Salida:   4 5 6 7 8 8

Entrada: A[] = {1, 3, 4, 5}, B] = {2, 4, 6, 8} 
Salida: 1 2 3 4 4 5 6 8

Entrada: A[] = {5, 8, 9}, B[] = {4, 7, 8} 
Salida: 4 5 7 8 8 9 

Enfoque: el problema dado, fusionar dos arrays ordenadas usando minheap ya existe. Pero aquí la idea es usar una cola de prioridad para implementar un montón mínimo proporcionado por STL . Siga los pasos a continuación para resolver el problema: 

• Inicialice una cola de prioridad mínima, digamos PQ , para implementar Min Heap.
• Atraviese la array A[] e inserte todos los elementos de la array en el PQ .
• Atraviese la array B[] e inserte todos los elementos de la array en el PQ .
• Ahora ponga todos los elementos del PQ en una array, digamos res[] haciendo estallar el elemento superior del PQ uno por uno.
• Finalmente, imprima la array ordenada res[] como respuesta.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to merge two arrays
void merge(int A[], int B[], int N, int M)
{
    // Stores the merged array
    int res[N + M];
 
    // Create a min priority_queue
    priority_queue<int, vector<int>, greater<int> > pq;
 
    // Traverse the array A[]
    for (int i = 0; i < N; i++)
        pq.push(A[i]);
 
    // Traverse the array B[]
    for (int i = 0; i < M; i++)
        pq.push(B[i]);
 
    int j = 0;
 
    // Iterate until the
    // pq is not empty
    while (!pq.empty()) {
 
        // Stores the top element
        // of pq into res[j]
        res[j++] = pq.top();
 
        // Removes the top element
        pq.pop();
    }
 
    // Print the merged array
    for (int i = 0; i < N + M; i++)
        cout << res[i] << ' ';
}
 
// Driver Code
int main()
{
 
    // Input
    int A[] = { 5, 6, 8 };
    int B[] = { 4, 7, 8 };
 
    int N = sizeof(A) / sizeof(A[0]);
    int M = sizeof(B) / sizeof(B[0]);
 
    // Function call
    merge(A, B, N, M);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to merge two arrays
static void merge(int A[], int B[], int N, int M)
{
     
    // Stores the merged array
    int []res = new int[N + M];
     
    // Create a min priority_queue
    Queue<Integer> pq = new PriorityQueue<>();
     
    // Traverse the array A[]
    for(int i = 0; i < N; i++)
        pq.add(A[i]);
     
    // Traverse the array B[]
    for(int i = 0; i < M; i++)
        pq.add(B[i]);
     
    int j = 0;
     
    // Iterate until the
    // pq is not empty
    while (!pq.isEmpty())
    {
         
        // Stores the top element
        // of pq into res[j]
        res[j++] = pq.peek();
     
        // Removes the top element
        pq.remove();
    }
     
    // Print the merged array
    for(int i = 0; i < N + M; i++)
        System.out.print(res[i] + " ");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Input
    int A[] = { 5, 6, 8 };
    int B[] = { 4, 7, 8 };
 
    int N = A.length;
    int M = B.length;
 
    // Function call
    merge(A, B, N, M);
}
}
 
// This code is contributed by todaysgaurav

# Python3 program for the above approach
from queue import PriorityQueue
 
# Function to merge two arrays
def merge(A, B, N, M):
 
    # Stores the merged array
    res = [0 for i in range(N + M)]
     
    # Create a min priority_queue
    pq = PriorityQueue()
     
    # Traverse the array A[]
    for i in range(N):
        pq.put(A[i])
         
    # Traverse the array B[]
    for i in range(M):
        pq.put(B[i])
 
    j = 0
     
    # Iterate until the
    # pq is not empty
    while not pq.empty():
       
        # Removes the top element and
        # stores it into res[j]
        res[j] = pq.get()
        j += 1
         
    # Print the merged array
    for i in range(N + M):
        print(res[i], end = " ")
         
    # return back to main
    return
 
# Driver code
if __name__ == '__main__':
   
    # Input
    A = [ 5, 6, 8 ]
    B = [ 4, 7, 8 ]
 
    N = len(A)
    M = len(B)
     
    # Function call
    merge(A, B, N, M)
     
# This code is contributed by MuskanKalra1

<script>
 
// Javascript program for the above approach
 
// Function to merge two arrays
function merge(A, B, N, M)
{
 
    // Stores the merged array
    var res = Array(N+M).fill(0);
 
    // Create a min priority_queue
    var pq = [];
 
    // Traverse the array A[]
    for (var i = 0; i < N; i++)
        pq.push(A[i]);
 
    // Traverse the array B[]
    for (var i = 0; i < M; i++)
        pq.push(B[i]);
 
    var j = 0;
    pq.sort((a,b)=>b-a);
 
    // Iterate until the
    // pq is not empty
    while (pq.length!=0) {
 
        // Stores the top element
        // of pq into res[j]
        res[j++] = pq[pq.length-1];
 
        // Removes the top element
        pq.pop();
        pq.sort((a,b)=>b-a);
    }
 
    // Print the merged array
    for (var i = 0; i < N + M; i++)
        document.write(res[i] + ' ');
}
 
// Driver Code
// Input
var A = [5, 6, 8];
var B = [4, 7, 8];
var N = A.length;
var M = B.length;
 
// Function call
merge(A, B, N, M);
 
// This code is contributed by rrrtnx.
</script>

4 5 6 7 8 8 

Complejidad de tiempo: O((N+M)*log(N+M))
Espacio auxiliar: O(N+M)