Объедините два отсортированных массива, используя очередь приоритетов

Имея два отсортированных массива A[] и B[] размеров N и M соответственно, задача состоит в том, чтобы объединить их отсортированным образом.

Примеры:

Input: A[] = { 5, 6, 8 }, B[] = { 4, 7, 8 }
Output:  4 5 6 7 8 8

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

Input: A[] = {5, 8, 9}, B[] = {4, 7, 8} 
Output: 4 5 7 8 8 9 

Подход: данная проблема, объединяющая два отсортированных массива с использованием minheap, уже существует. Но здесь идея состоит в том, чтобы использовать priority_queue для реализации min-heap, предоставляемого STL. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте очередь с минимальным приоритетом, скажем, PQ , чтобы реализовать Min Heap.
• Пройдите массив A[] и поместите все элементы массива в PQ .
• Пройдитесь по массиву B[] и поместите все элементы массива в PQ .
• Теперь поместите все элементы PQ в массив, скажем, res[] , извлекая верхний элемент PQ один за другим.
• Наконец, выведите отсортированный массив res[] в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O((N+M)*log(N+M))
Вспомогательное пространство: O(N+M)