Объединение отсортированных массивов

Question

Возможные дубликаты:
Объединение двух отсортированных списков
Алгоритм N-way слияния

Учитывая k отсортированных массивов, каждый из которых имеет длину n, создайте один объединенный и отсортированный массив. Ориентация на время выполнения и сложность пространства.

Источник: вопрос об интервью Amazon.
Какие-нибудь мысли? Спасибо

Answer 1

Создайте кучу из первого элемента в каждом массиве. Извлеките элемент head из кучи, вставьте его в массив результатов, а затем возьмите следующий элемент из массива, из которого получена голова кучи, и вставьте его в кучу. Повторяйте, пока вы не будете использовать все массивы.